[Gym103960B] Fun with Stones

并不是多困难或者有趣的题，写sol仅仅是因为觉得好笑（）。

题目大意

三堆石子 Nim 游戏，第 $i$ 堆石子数量在 $[l_i,r_i]$ 中随机，求先手必胜的概率，对 $10^9+7$ 取模。

$l_i,r_i\le 10^9$。

题解

说人话就是求三个数异或起来不为0的概率，很容易想到数位dp，由于只有三个数，硬求就好了。

那么为什么我上面写到 “觉得好笑” 呢。

因为听说有个很高妙的写法十几分钟就可以写完，可我是sb我不会，然后很正经地写了个27类巨大分讨6k数位dp，更好笑的是写完居然一遍过了（）。事后知道有高妙写法的我：(ｉДｉ) 。

还是大概说一下，先算出异或和为0的方案数最后减一下除以总数即可。区间比较难求那就dp求出范围分别小于 $x,y,z$ 的然后容斥一下即可。dp具体实现就是 $f_{i,0/1,0/1,0/1}$ ，代表现在考虑到第 $i$ 位、第一个数是否顶着上界、第二个数是否顶着上界、第三个数是否顶着上界的方案数。转移时分别枚举三个数在这一位上是 0/1，三个数的当前位置分别和上界当前位置比较大小再自己算一下这一位可以从哪些状态转移过来即可。

复杂度也许是 $log$ 带巨大常数，总之能过。

Code

写得很蠢，但是因为很好笑所以还是贴上来吧，就当看个乐子。

#include<bits/stdc++.h>
using namespace std;const int N=35,mod=1e9+7;int l1,r1,l2,r2,l3,r3,ans,f[N][2][2][2];int solve(int x,int a,int a1,int b,int b1,int c,int c1){int res=0;for(int i=a;i<=a1;i++)for(int j=b;j<=b1;j++)for(int k=c;k<=c1;k++)res=(res+f[x][i][j][k])%mod;return res;
}int work(int a,int b,int c){memset(f,0,sizeof(f));f[32][1][1][1]=1;for(int i=31,x,y,z;i>=0;i--){x=((a>>i)&1),y=((b>>i)&1),z=((c>>i)&1);for(int a1=0;a1<=1;a1++)for(int b1=0;b1<=1;b1++)for(int c1=0;c1<=1;c1++){if((a1^b1^c1)!=0) continue;if(a1<x){if(b1<y){if(c1<z) f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,1,0,1))%mod;else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,1,0,1,1,1))%mod;}else f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,1,0,0))%mod;}else if(b1==y){if(c1<z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,1))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,1,1,1,0,1))%mod;}else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,1,1,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,1,0,0,1,1))%mod;f[i][0][1][1]=(f[i][0][1][1]+solve(i+1,0,1,1,1,1,1))%mod;}else{f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,1,1,1,0,0))%mod;}}else{if(c1<z) f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,1))%mod;else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,1,0,0,1,1))%mod;}else f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,1,0,0,0,0))%mod;}}else if(a1==x){if(b1<y){if(c1<z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,1,0,1))%mod;}else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,1,1,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,1,0,0))%mod;f[i][1][0][1]=(f[i][1][0][1]+solve(i+1,1,1,0,1,1,1))%mod;}else{f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,0))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,1,0,0))%mod;}}else if(b1==y){if(c1<z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,1))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,1))%mod;f[i][1][1][0]=(f[i][1][1][0]+solve(i+1,1,1,1,1,0,1))%mod;}else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,0,1,1))%mod;f[i][0][1][1]=(f[i][0][1][1]+solve(i+1,0,0,1,1,1,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,0))%mod;f[i][1][1][0]=(f[i][1][1][0]+solve(i+1,1,1,1,1,0,0))%mod;f[i][1][0][1]=(f[i][1][0][1]+solve(i+1,1,1,0,0,1,1))%mod;f[i][1][1][1]=(f[i][1][1][1]+solve(i+1,1,1,1,1,1,1))%mod;}else{f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,0))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,0))%mod;f[i][1][1][0]=(f[i][1][1][0]+solve(i+1,1,1,1,1,0,0))%mod;}}else{if(c1<z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,1))%mod;}else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,0,1,1))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,0))%mod;f[i][1][0][1]=(f[i][1][0][1]+solve(i+1,1,1,0,0,1,1))%mod;}else{f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][1][0][0]=(f[i][1][0][0]+solve(i+1,1,1,0,0,0,0))%mod;}}}else{if(b1<y){if(c1<z) f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,1))%mod;else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,1,1,1))%mod;}else f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,1,0,0))%mod;}else if(b1==y){if(c1<z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,1))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,1))%mod;}else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,0,1,1))%mod;f[i][0][1][1]=(f[i][0][1][1]+solve(i+1,0,0,1,1,1,1))%mod;}else{f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][1][0]=(f[i][0][1][0]+solve(i+1,0,0,1,1,0,0))%mod;}}else{if(c1<z) f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,1))%mod;else if(c1==z){f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;f[i][0][0][1]=(f[i][0][0][1]+solve(i+1,0,0,0,0,1,1))%mod;}else f[i][0][0][0]=(f[i][0][0][0]+solve(i+1,0,0,0,0,0,0))%mod;}}}}return solve(0,0,1,0,1,0,1);
}int qpow(int x,int y){int res=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1) res=1ll*res*x%mod;return res;
}int main(){scanf("%d%d%d%d%d%d",&l1,&r1,&l2,&r2,&l3,&r3);ans=((work(r1,r2,r3)-work(l1-1,r2,r3)-work(r1,l2-1,r3)-work(r1,r2,l3-1)+work(l1-1,l2-1,r3)+work(l1-1,r2,l3-1)+work(r1,l2-1,l3-1)-work(l1-1,l2-1,l3-1))%mod+mod)%mod;int az=1ll*(r1-l1+1)*(r2-l2+1)%mod*(r3-l3+1)%mod;printf("%d",1ll*(az-ans+mod)%mod*qpow(az,mod-2)%mod);return 0;
}

看这幽默的代码不去做大模拟真的可惜了。