[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

发布于 2018-02-22  175 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

Description

Given integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 15), compute the number of sequences a1, ..., aN such that:
0 ≤ ai < 2M
ai is not divisible by ci (0 < ci ≤ 2M)
ai & ai+1 = 0 (that is, ai and ai+1 have no common bits in their binary representation)

Http

SPOJ

Tag

动态规划,高维前缀和

题目大意

给出一列数,要求求出满足条件的数列的方案数。

解决思路

由数据范围容易想到,设\(F[i][j]\)表示前\(i\)个数,第\(i\)个数是\(j\)的方案数,那么有转移方程
\[ F[i][j]=\sum_{k\&j==0} F[i-1][k]\]
不难发现,这里要求的\(k\)就是\(j\)的补集的子集,为了方便计算,我们可以记\(Sum[S]\)表示\(S\)及\(S\)子集的方案数总和,需要的时候直接赋值进去就好。
怎么求这个呢?这里用到一种叫做高维前缀和的科技,可以在\(O(n*2^n)\)时间范围内求得子集之和。具体来说,是这样

for (int i=0;i<m;i++)
    for (int j=0;j<(1<<m);j++)
        if ((j&(1<<i))!=0) Sum[j]+=Sum[j^(1<<i)];

正确性暂不会证明。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=51;
const int maxM=15;
const int Mod=1000000000;
const int inf=2147483647;

int n,m;
int C[maxN];
ll F[maxN][1<<(maxM+1)];
ll Sum[1<<(maxM+1)];

int main()
{
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while (T--)
    {
        cin>>n>>m;
        for (int i=1;i<=n;i++) cin>>C[i];
        mem(F,0);mem(Sum,0);
        //先把第一位的方案计算出来
        for (int i=0;i<(1<<m);i++) if (i%C[1]!=0) F[1][i]=Sum[i]=1;
        for (int i=0;i<m;i++)//高维前缀和
            for (int j=0;j<(1<<m);j++)
                if ((j&(1<<i))!=0) Sum[j]=(Sum[j]+Sum[j^(1<<i)])%Mod;
        for (int i=2;i<=n;i++)
        {
            for (int j=0;j<(1<<m);j++) if (j%C[i]!=0) F[i][j]=Sum[j^((1<<m)-1)];//转移
            mem(Sum,0);//准备统计新的一次的答案
            for (int j=0;j<(1<<m);j++) Sum[j]=F[i][j];
            for (int j=0;j<m;j++)//高维前缀和
                for (int k=0;k<(1<<m);k++)
                    if ((k&(1<<j))!=0) Sum[k]=(Sum[k]+Sum[k^(1<<j)])%Mod;
        }
        ll Ans=0;
        for (int i=0;i<(1<<m);i++) if (i%C[n]!=0) Ans=(Ans+F[n][i])%Mod;
        printf("%lld\n",Ans);
    }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)


HNCJ OIer