2018.10.25 uestc上天的卿学姐（计数dp）

传送门 看了$DZYO$的题解之后发现自己又$sb$了啊。 直接$dp$是$O(2^d)$更新，$O(1)$查询或者$O(1)$更新，$O(2^n)$查询的。 然后我就不会了233. 显然可以利用分块暴力的思想。 每次枚举前半段来计算当前答案，然后枚举后半段来更新$dp$数组。 这样效率$O(n\ast 2^{\frac{d}{2}})$可以通过全部测试点。 代码：

#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } inline int read_2(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<1)+(ch^48),ch=getchar(); return ans; } const int mod=1e9+7,lim=1<<8; int f[lim+5][lim+5],n,d,ans=0; int main(){ n=read(),d=read(); for(int i=1;i<=n;++i){ int x=read_2(),fi=x>>8,se=x^(fi<<8),stat,sum=1; for(stat=fi;;stat=fi&(stat-1)){ (sum+=f[stat][se])%=mod; if(!stat)break; } for(stat=se;stat<lim;stat=se|(stat+1))(f[fi][stat]+=sum)%=mod; } for(int i=0;i<lim;++i)(ans+=f[i][lim-1])%=mod; cout<<ans; return 0; }