NOI2001方程的解数
题目描述
已知一个n元高次方程：
其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。
假设未知数1≤ xi ≤M, i=1,,,n，求这个方程的整数解的个数。
输入
文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。
输出
文件仅一行，包含一个整数，表示方程的整数解的个数。
样例输入
3 150 1 2 -1 2 1 2
样例输出
178
提示
约束条件
方程的整数解的个数小于231。
★本题中，指数Pi(i=1,2,……,n)均为正整数。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <cmath> #include <cstring> #include <cstdio> #define mod 12313813 using namespace std; struct data {int value,num; }hash[mod]; int n,m; int k[10],p[10],pd[153][153]; int ans; inline int HASH(int value) { int lc=int(abs(value))%mod; while(hash[lc].num>0&&hash[lc].value!=value) lc=(lc+1)%mod; return lc; } void dfs1(int nod,int value) { if(nod>n/2) { int x=HASH(value); hash[x].num++; hash[x].value=value; return; } for(int i=1;i<=m;i++) { dfs1(nod+1,value+k[nod]*pd[i][p[nod]]); } } void dfs2(int nod,int value) { if(nod>n) { int x=HASH(value); ans+=hash[x].num; return; } for(int i=1;i<=m;i++) dfs2(nod+1,value-k[nod]*pd[i][p[nod]]); } int main() { for (int i=0;i<=150;i++){ pd[i][0]=1; for (int j=1;j<=150;j++) pd[i][j] = pd[i][j-1]*i; } cin>>n>>m; for (int i=1;i<=n;i++) cin>>k[i]>>p[i]; ans=0; dfs1(1,0); dfs2(n/2+1,0); cout<<ans; return 0; } |
计数器 9854560
OI 课件=>
OI 课件=>
报告黄学长，mod太大，在codevs上爆空间了
很是不明白为什么搜一半查一半
meet in the middle 为了降低复杂度