题解 SP2829 【TLE - Time Limit Exceeded】
看了一下,几篇题解都是二维数组的dp。
我这里有一维的做法,简单介绍一下,供参考。
转化条件:
等价于
而利用高位前缀和,我们可以这样枚举子集求前缀和:
for(int i=1;i<m;i++)
for(int j=0;j<(1<<m);j++)
if((1<<i)&j)f[j]+=f[j^(1<<i)];
这段代码的意思是:
枚举每一个二进制位,加上这个维度的值。
但是此题要求的是
所以我们在求完后将其翻转,像这样:
for(int i=1;i<(1<<m-1);i++)
swap(f[i],f[(1<<m)-1-i]);
最后,如果它不符合
像这样:
for(int i=0;i<(1<<m);i++)
if(i%c[j]==0)f[i]=0;
那么这道题就讲完了。
具体参照代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
int f[1000000];
int t,n,m,a[50];
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<(1<<m);i++)
f[i]=(i%a[1]!=0);
for(int i=2;i<=n;i++){
for(int j=0;j<m;j++)
for(int k=0;k<(1<<m);k++)
if((1<<j)&k)f[k]=(f[k]+f[k^(1<<j)])%mod;
for(int j=0;j<(1<<m-1);j++)
swap(f[j],f[(1<<m)-1-j]);
for(int j=0;j<(1<<m);j++)
if(j%a[i]==0)f[j]=0;
}
int ans=0;
for(int i=0;i<(1<<m);i++)
ans=(ans+f[i])%mod;
printf("%d\n",ans);
}
return 0;
}