SPOJ Time Limit Exceeded

【题意】

【解题方法】

Wannafly的每日一题，通过这个题我学到了新的知识。就是维护如何维护高维前缀和。这个题首先不考虑c[i]的限制，我们可以想到一个dp，就是dp[i][j]表示长度为i的序列以j结尾的方案数。显然有dp[i][j] = sum(dp[i-1][k])，这里对所有满足j&k=0的k求和。然后k & j = 0 等价于 k & (~j) = k，推得k是~j的一个子集。然后我们让fp[i][j] = dp[i][~j]，即是fp[i][j] = sum(dp[i-1][k])，即是对所有j的子集求和。实际上这个方程的形式还有一个别名，高维前缀和，这里的每一维大小都是2。联想到二维前缀和，可以通过每一行分别做一次前缀和之后每一列分别做一次前缀和得到二维前缀和，推广到高维前缀和，只需依次对每一维，把这一维是0的状态加到这一维是1的状态上去即可，
对于c[i]的限制，在求出所有dp[i][j]之后把满足j是c[i]的倍数的状态清零即可，然后这题就做完了。

【时间复杂度】 O(n*m*2^m)

【AC代码】空间复杂度 O(n*m*2^m) 这题还可以滚动数组优化一下，可以变成O(m*2^m)

//
//Created by just_sort 2016/1/3
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 100;
const int maxm = 2e5;
const int maxs = 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1000000000;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int dp[55][1<<16];
int c[55];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        CLR(dp, 0);
        int n, m;
        scanf("%d%d", &n, &m);
        REP2(i, 1, n) scanf("%d", &c[i]);
        int all = (1 << m) - 1;
        REP2(s, 0, all) if(s % c[1] != 0) dp[1][s] = 1;
        REP2(i, 2, n){
            REP2(s, 0, all) dp[i][s ^ all] = dp[i - 1][s];
            REP1(j, 0, m){
                REP2(s, 0, all){
                    if(s & (1<<j)){
                        dp[i][s^(1<<j)] += dp[i][s];
                        if(dp[i][s^(1<<j)] >= mod) dp[i][s^(1<<j)] -= mod;
                    }
                }
            }
            REP2(s, 0, all){
                if(s % c[i] == 0) dp[i][s] = 0;
            }
        }
        int ans = 0;
        REP2(s, 0, all){
            ans += dp[n][s];
            if(ans >= mod) ans -= mod;
        }
        cout << ans << endl;
    }
    return 0;
}

【贴一下Wannafly滚动数组的版本吧】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int Mod=1000000000;
inline void add(int &x,int y)
{
    if((x+=y)>=Mod)x-=Mod;
    if(x<0)x+=Mod;
}
int c[55],dp[1<<15];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(int j=0;j<(1<<m);j++)
            dp[j]=(j==0);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<(1<<m);j+=2)
                swap(dp[j],dp[j^((1<<m)-1)]);
            for(int j=0;j<m;j++)
                for(int k=0;k<(1<<m);k++)
                    if(~k&(1<<j))add(dp[k],dp[k|(1<<j)]);
            for(int j=0;j<(1<<m);j+=c[i])
                dp[j]=0;
        }
        int res=0;
        for(int j=0;j<(1<<m);j++)
            add(res,dp[j]);
        printf("%d\n",res);
    }
    return 0;
}