题目
传送门 https://www.luogu.com.cn/problem/P2150
思路
比较恶心的一道状压
如果你一开始就看最大范围,
你的心中可能一点想法都没有
但是如果你从最小的数据开始看
也就是 \(n\le 30\)
如果你对质数足够熟悉的话
那么你会发现 30 以内的质数是 10
还有一点, 题目中对不和谐度的描述最关键的一点是互质
这说明了什么?
30 分的思路时间复杂度极可能为 \(O(n*2^n*2^n)\)
也就是状压,\(2^n\) 的意义就为在二进制下, 第 i 个质数是否出现
之后我们就可以很简单的统计出来.
很显然这个做法是可以推广的
我们依然是存一个二进制, 之后多存一个变量来针对剩下的质数, 也就是超过 \(\sqrt n\) 的大质数
很显然, 对于一个美味度, 大质数只有一个
我们可以设 \(f_{i,j}\) 为小 G 拿的数的所有的质因数的状态为 i, 小 W 拿的数的所有的质因数状态为 j
但是我们发现这个状态并没有考虑大质数的情况
我们再设 \(dp_{n,i,j,t}\) 表示第 n 个大质数属于 i 状态还是 j 状态, t 为 1 就是属于 i 集合, 反之则为 j 集合
比较好想的是 \(n\) 的那一位可以直接滚掉
我们先将所有美味度分解,
再按大质数的大小从小到大排序
之后就是状压的标准操作
枚举两个集合
如果两个集合没有相交, 也就是 & 之后为 0
你就把当前的美味度塞进去即可
转移方程即为
\(dp_{j|sus[i].sta,k,1}+=dp_{j,k,1}\)
当然, 同理, 当前这个美味度也可以塞到 k 集合,
\(dp_{j,k|sus[i].sta,0}+=dp_{j,k,0}\)
我们再想大质数怎么办
如果 \(sus[i].p!=sus[i-1].p\)
就用一个类似于刷表的方式
\(dp_{i,j,0}=dp_{i,j,1}=f_{i,j}\)
如果 \(sus[i].p!=sus[i+1].p\)
同上
\(f_{i,j}=dp_{i,j,1}+dp_{i,j,0}-f_{i,j}\)
代码
- #include<iostream>
- #include<algorithm>
- using namespace std;
- #define int long long
- struct node
- {
- int sta;
- int p;
- friend bool operator <(const node &a,const node &b)
- {
- return a.p<b.p;
- }
- }sus[505];
- int n,mod;
- int pri[10]={2,3,5,7,11,13,17,19};
- int dp[(1<<10)][(1<<10)][2];
- int f[(1<<10)][(1<<10)];
- long long ans;
- signed main()
- {
- cin>>n>>mod;
- f[0][0]=1;
- for(int i=2;i<=n;i++)
- {
- int t=i;
- for(int j=0;j<=7;j++)
- {
- if(t%pri[j]==0)
- {
- sus[i].sta|=(1<<j);
- while(t%pri[j]==0)
- t/=pri[j];
- }
- }
- sus[i].p=t;
- }
- sort(sus+2,sus+n+1);
- for(int i=2;i<=n;i++)
- {
- if(sus[i].p==1||sus[i].p!=sus[i-1].p)
- {
- for(int j=0;j<(1<<8);j++)
- {
- for(int k=0;k<(1<<8);k++)
- {
- dp[j][k][0]=dp[j][k][1]=f[j][k];
- }
- }
- }
- for(int j=(1<<8)-1;j>=0;j--)
- {
- for(int k=(1<<8)-1;k>=0;k--)
- {
- if((sus[i].sta&k)==0)
- {
- dp[j|sus[i].sta][k][1]=(dp[j|sus[i].sta][k][1]+dp[j][k][1])%mod;
- }
- if((sus[i].sta&j)==0)
- {
- dp[j][k|sus[i].sta][0]=(dp[j][k|sus[i].sta][0]+dp[j][k][0])%mod;
- }
- }
- }
- if(sus[i].p==1||sus[i].p!=sus[i+1].p)
- {
- for(int j=0;j<(1<<8);j++)
- {
- for(int k=0;k<(1<<8);k++)
- {
- f[j][k]=((dp[j][k][0]+dp[j][k][1]-f[j][k])%mod+mod)%mod;
- }
- }
- }
- }
- for(int i=0;i<(1<<8);i++)
- {
- for(int j=0;j<(1<<8);j++)
- {
- if((i&j)==0)
- {
- ans=(ans+f[i][j])%mod;
- }
- }
- }
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3343068.html