首页 > 其他 > 详细

CF895C Square Subsets (组合数+状压DP+简单数论)

时间:2018-09-24 22:49:53      阅读:205      评论:0      收藏:0      [点我收藏+]

题目大意:给你一个序列,你可以在序列中任选一个子序列,求子序列每一项的积是一个平方数的方案数。

1<=a[i]<=70

因为任何一个大于2的数都可以表示成几个质数的幂的乘积

所以我们预处理70以内的质数,把它作为二进制状压的状态,每个在序列中出现数Hash一下,组合数推一下

所以把奇次幂的状态表示为1,偶次幂的状态就是0,比如6就是11,42就是1011

而平方数的每个质因子的指数都是偶数,所以最终结果的状态就是0000000...

转移的过程,两个数的乘积,就是这两个数的质因子二进制的状态的合并,即异或(xor)运算

卡常很恶心,懒得进一步优化了

好吧据说可以推出结论,这个组合数加起来其实是2的幂次

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #define N 100100
 5 #define M 75
 6 #define mod 1000000007
 7 #define C(m,n) (((fac[n]*inv[m])%mod*inv[n-m])%mod)
 8 #define ll long long 
 9 using namespace std;
10 
11 int xx,n,now,lst;
12 int hx[M];
13 ll x,y,t;
14 ll inv[N],fac[N],f[2][(1<<19)+100];
15 int pr[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
16 int gc()
17 {
18     int rett=0,fh=1;char c=getchar();
19     while(c<0||c>9) {if(c==-)fh=-1; c=getchar();}
20     while(c>=0&&c<=9) {rett=rett*10+c-0;c=getchar();}
21     return rett*fh;
22 }
23 void exgcd(ll a,ll b)
24 {
25     if(b==0) {x=1,y=0;}
26     else {exgcd(b,a%b);t=x;x=y;y=t-a/b*y;}
27 }
28 void get_inv()
29 {
30     inv[0]=inv[1]=1,fac[0]=fac[1]=1;
31     for(ll i=2;i<=n;i++) 
32     {
33         exgcd(i,mod);
34         fac[i]=(fac[i-1]*i)%mod;
35         x=(x%mod+mod)%mod;
36         inv[i]=(inv[i-1]*x)%mod;
37     }
38 }
39 
40 int main()
41 {
42     //freopen("aa.in","r",stdin);
43     scanf("%d",&n);
44     for(int i=1;i<=n;i++) xx=gc(),hx[xx]++;
45     get_inv();
46     now=1,lst=0,f[0][0]=1;
47     for(int i=1;i<=70;i++)
48     {
49         if(!hx[i]) continue;
50         int s=0,x=i;
51         for(int j=0;j<19;j++)
52         {
53             while(x%pr[j]==0) 
54             {
55                 s^=(1<<j);
56                 x/=pr[j];
57             }
58         }
59         for(int p=0;p<(1<<19);p++)
60         {
61               if(!f[lst][p]) continue;
62             for(int j=0;j<=hx[i];j++)
63             {
64                 if(j&1)
65                 {
66                     f[now][p^s]+=(f[lst][p]*C(j,hx[i]))%mod;
67                     f[now][p^s]%=mod;
68                 }else{
69                     f[now][p]+=(f[lst][p]*C(j,hx[i]))%mod;
70                     f[now][p]%=mod;
71                 }  
72             }
73             f[lst][p]=0;
74         }
75         swap(now,lst);
76     }
77     printf("%I64d\n",f[lst][0]-1);
78     return 0;
79 }
80 
81     
82     

 

CF895C Square Subsets (组合数+状压DP+简单数论)

原文:https://www.cnblogs.com/guapisolo/p/9696976.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!