SPOJ Time Limit Exceeded（高維字首和）

【題目連結】 http://www.spoj.com/problems/TLE/en/

【題目大意】

　　給出n個數字c，求非負整數序列a，滿足a<2^m

　　并且有a[i]&a[i+1]=0，對于每個a[i]，要保證a[i]不是c[i]的倍數，

　　求這樣的a[i]序列的個數

【題解】

　　我們用dp[i]表示以i為結尾的方案數，

　　我們發現要滿足a[i]&a[i+1]=0,則dp[i]是從上一次結果中所有滿足i&j=0的地方轉移過來的

　　i&j=0即i&(~j)=i，即i為~j的子集，那麼我們每次對上一次的結果進行下标取反操作，

　　那麼求目前dp[i]，就是求出以i為子集的上一次計算出的dp值的高維字首和。

　　對于c[i]這個條件，我們每輪計算後将c[i]倍數為下标的dp值置0即可。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,n,m,c[100];
const int mod=1000000000;
struct data{
    int val;
    data operator +(const data &rhs)const{
        int t_val=val+rhs.val;
        if(t_val>=mod)t_val-=mod;
        if(t_val<0)t_val+=mod;
        return data{t_val};
    }
}dp[(1<<15)+10],res;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&c[i]);
        int all=1<<m;
        for(int j=0;j<all;j++)dp[j].val=(j==0);
        for(int i=1;i<=n;i++){
            for(int j=0;j<all;j+=2)swap(dp[j],dp[j^(all-1)]);
            for(int j=0;j<m;j++)for(int k=0;k<all;k++){
                if(~k&(1<<j))dp[k]=dp[k]+dp[k|(1<<j)];
            }for(int j=0;j<all;j+=c[i])dp[j].val=0;
        }res.val=0;
        for(int j=0;j<all;j++)res=res+dp[j];
        printf("%d\n",res.val);
    }return 0;
}