首页 > 代码库 > SPOJ Time Limit Exceeded（高维前缀和）
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;}SPOJ Time Limit Exceeded（高维前缀和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。