SPOJ Time Limit Exceeded(高维前缀和)
2024-09-30 05:49:47
【题目链接】 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;
}
最新文章
- entrar en su zapatilla de deporte en este lugar
- Java 创建过滤器 解析xml文件
- LinQ To Object 基本用法
- python有序查找算法:二分法
- UVa 11572 (滑动窗口) Unique Snowflakes
- NOI题库1814 恼人的青蛙
- PHP获取真实的网络IP
- service and intentservice
- [svn] TortoiseSVN 图文操作
- bzoj2876 [NOI2012]骑行川藏(拉格朗日乘数法)
- 19.JavaScript
- shell的进度条【转】
- Linux下 查找大文件
- 关于A left join B,A是否一定是主表?
- Servlet Exception and Error Handling
- [zoj4046][树状数组求逆序(强化版)]
- html5 canvas画布上合成
- 苹果ANCS协议学习【转】
- 【LOJ】#2116. 「HNOI2015」开店
- Intelli公司IDE快捷键设置
热门文章
- 14、char和varchar的区别?
- MSSQL 视图/事务(TRAN[SACTION])/存储过程(PROC[EDURE])/触发器(TRIGGER )
- 关于win7局域网共享的相关设置
- CentOS7安装MySQL5.7以及修改密码
- Git常规配置与基本用法
- 64_l4
- quazip 在windows msvc 2005 下的编译
- VPS L2TP配置
- VPS性能测试(2):内存大小、交换空间、高速缓存、实际使用内存
- 动画基础--基于Core Animation(3)