题解 SP2829 【TLE - Time Limit Exceeded】

· · 题解

看了一下，几篇题解都是二维数组的dp。

我这里有一维的做法，简单介绍一下，供参考。

转化条件：

a_i$&$a_{i+1}=0

等价于a_i是2^m-1-a_{i+1}的子集。

而利用高位前缀和，我们可以这样枚举子集求前缀和：

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)];

这段代码的意思是：

枚举每一个二进制位，加上这个维度的值。

但是此题要求的是2^m-1-a_{i+1}的子集和。

所以我们在求完后将其翻转，像这样：

for(int i=1;i<(1<<m-1);i++)
    swap(f[i],f[(1<<m)-1-i]);

最后，如果它不符合a_i%c_i!=0就将其制0。

像这样：

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;
}