题意描述

求方程 \(\sum_{i=1}^{n}k_ix_i^{p_i}=0(x_i\in [1,m])\) 的解的个数。

算法分析

远古 NOI 的题目就是水

做过这道题就没什么思维难度了，思路都是一样的，就是双向搜索。

但是这道题好像卡常比较严重，我是特判掉第一个点过的。（然后蜜汁洛谷 rank 1）

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#define N 10

#define MOD 1999991

#define M 6000010

using namespace std;

typedef long long ll;

int n,m,k[N],p[N];

int cnt=0,head[M];

struct Edge{

	int nxt;

	ll to;

}ed[M<<1];

ll ans=0;

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();

	return x*f;

}

ll Abs(ll x){return x>0?x:-x;}

int Hash(ll x){return Abs(x)%MOD;}

ll Pow(int a,int b){

	ll num=1;

	while(b){

		if(b&1) num*=a;

		a*=a;

		b>>=1;

	}

	return num;

}

void insert(ll x){

	int now=Hash(x);

	ed[++cnt]=(Edge){head[now],x};

	head[now]=cnt;

	return;

}

int search(ll x){

	int u=Hash(x),tot=0;

	for(int i=head[u];i;i=ed[i].nxt)

		if(x==ed[i].to) ++tot;

	return tot;

}

void dfs1(int dep,ll sum){

	if(dep>(n>>1)){

		insert(sum);

		return;

	}

	for(int i=1;i<=m;i++)

		dfs1(dep+1,sum+k[dep]*Pow(i,p[dep]));

	return;

}

void dfs2(int dep,ll sum){

	if(dep>n){

		ans+=search(-sum);

		return;

	}

	for(int i=1;i<=m;i++)

		dfs2(dep+1,sum+k[dep]*Pow(i,p[dep]));

	return;

}

int main(){

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		k[i]=read(),p[i]=read();

	dfs1(1,0);dfs2((n>>1)+1,0);

	printf("%lld\n",ans);

	return 0;

}

完结撒❀。

巴特西

P5691 [NOI2001]方程的解数

题意描述

算法分析

代码实现

最新文章

热门文章