正题

---

题目大意

定义函数$f(x)(x$为一个序列$)$
若任意一个$x_i=1$那么有$f(x)=1$
若有一个$x_i=0$那么有$f(x)=0$
其他的，有$$f(x)=(\sum _{j=1}^{n}f(x_1...,x_j-1,...x_n))\%2$$
给出$l_i,r_i$，求$$\sum _{l_i\le x_i\le r_i}f(x)$$

---

解题思路

我们发现对于$x$有$f(x)={\prod }_{i=1}^{n-1}{C}_{\sum x_j}^{x_i}$
然后又有$C_n^k$为奇数仅当$(n+k)\&k=k$
然后转换为$f(x)=1$的充要条件就是对于任意的$1\le i̸=j\le n$有$(x_i+x_j)\&x_i=x_i$，证明

然后我们数位$dp$，用$f_{i,j}$表示到第$i$位时状态$j$中0表示没有到达上界，$1$表示到达了上界。

对于$l_i$，我们可以对$n$维进行容斥即可。

时间复杂度$O(50\ast n\ast (2^n{)}^2)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=10,XJQ=990804011; ll T,n,l[N],r[N],x[N],f[60][1<<N],ans,MS; ll solve(ll S) {for(ll i=0;i<n;i++){x[i]=((S>>i)&1)?(l[i]-1):r[i];if(x[i]<0) return 0;}memset(f,0,sizeof(f));f[51][0]=1;for(ll i=50;i>=0;i--){for(ll j=0;j<MS;j++){if(!f[i+1][j]) continue;ll now=0;for(ll k=0;k<n;k++)now|=(1<<k)*(x[k]>>i&1);(f[i][j|now]+=(__builtin_popcount(j)+1)*f[i+1][j]+XJQ)%=XJQ;for(ll k=0;k<n;k++)if((now&(~j))>>k&1)(f[i][j|(now^(1<<k))]+=f[i+1][j]+XJQ)%=XJQ;}}ll ans=0;for(ll i=0;i<MS;i++)(ans+=f[0][i]+XJQ)%=XJQ;return ans; } int main() {freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%lld",&T);while(T--){scanf("%lld",&n);MS=1<<n;ans=0;for(ll i=0;i<n;i++)scanf("%lld%lld",&l[i],&r[i]),l[i]--,r[i]--;for(ll i=0;i<MS;i++)(ans+=(__builtin_popcount(i)&1?XJQ-solve(i):solve(i))+XJQ)%=XJQ;printf("%lld\n",ans);} } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的jzoj6344-[NOIP2019模拟2019.9.7]Huge Counting【组合数,状压dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。