小B写了一个程序，随机生成了n个正整数，分别是a[1]..a[n]，他取出了其中一些数，并把它们乘起来之后模p，得到了余数c。但是没过多久，小B就忘记了他选了哪些数，他想把所有可能的取数方案都找出来。你能帮他计算一下一共有多少种取数方案吗？请把最后的方案数模1000000007后输出。 小B记得他至少取了一个数。
对于30%的数据，n<=16; 另有30%的数据,p<=10000; 对于100%的数据，n<=32,p<=10^9,c<=10^9,a[i]
传说中的2^n算法能过30%. 另外百分之30考虑背包,用C作容量然后每一次取或不取
2^n大概能过n=20 考虑分治 先把n个数分成两组 (也就差不多一半,这个自己随便分,别超过20就好) 分开算每种余数方案数,用hash表存下 (STL黑科技map)
然后枚举一组的余数 假设是a 我们知道有ab=c(mod p) 转换为ab-kp=c用exgcd求解 解出b使得他在[0,p-1]这个区间内,这就是对应a的余数 然后将方案数一乘一加即可.
#include <cstdio> #include <iostream> #include <map> using namespace std; long long n,na,p,c,ans,sox,soy; map<long long,long long> ma,mb; //hashmap long long a[100]; long long abs(long long x) { return(x>0)?x:-x; } void dfs(int x,int ys) { if (x>na) { if (ys==c) ans++; ma[ys]++; return; } dfs(x+1,ys*a[x]%p); dfs(x+1,ys); } void dfs2(int x,int ys) { if (x>n) { if (ys==c) ans++; mb[ys]++; return; } dfs2(x+1,ys*a[x]%p); dfs2(x+1,ys); } long long gcd(long long a,long long b) { return (b)?gcd(b,a%b):a; } void exgcd(long long a,long long b) { if (b==0) { sox=1; soy=0; return; } exgcd(b,a%b); int tmp=sox; sox=soy; soy=tmp-a/b*soy; } int main() { ma.clear(); mb.clear(); cin>>n>>p>>c; if(c>=p) { printf("0"); return 0; } na=n/2; for (int i=1; i<=n; i++) cin>>a[i]; for (int i=1; i<=na; i++) dfs(i+1,a[i]); for (int i=na+1; i<=n; i++) dfs2(i+1,a[i]); map<long long,long long>::iterator it; for (it=mb.begin(); it!=mb.end(); it++) { int ys=it->first; sox=soy=0; exgcd(ys, p); long long gc=gcd(ys,p); if (c%gc!=0) continue; sox=sox*(c/gc)%p; if (sox<0) sox+=abs(sox)/p*p;; if (sox<0) sox+=p; while (sox<p) { if (ma[sox]!=0) { ans=(ans+ma[sox]*it->second)%1000000007; } sox+=p; } } cout<<ans<<endl; }