[SRM603] WinterAndSnowmen

Sol

设 \(A=\text{XOR}(X)\),\(B=\text{XOR}(Y)\)。

因为 \(A<B\)，所以写下他们的二进制表示，一定是最高的几位先是相等，紧接着有一位 \(A=0\) 而 \(B=1\)，后边就随意了。

嗯那我们可以枚举 \(A\) 和 \(B\) 二进制的 \(LCP\) 长度，这样计数就不重不漏了。

设当前枚举的长度为 \(p\), \(f[i][j][0/1][0/1]\) 表示决策完数字 \(i\)，\(A\) 的前 \(p\) 位异或上 \(B\) 的前 \(p\) 位的结果为 \(j\)，\(A/B\) 的第 \(p-1\) 位为 \(0/1\)。

转移就是决策当前数字填在哪个集合，最后的答案就是 \(f[n][0][0][1]\)。

Code #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; const int mod=1e9+7; class WinterAndSnowmen{ public: int f[2005][2049][2][2]; int getNumber(int n,int m){ int ans=0,mx=max(n,m); for(int i=11;i;i--){ memset(f,0,sizeof f); f[0][0][0][0]=1; for(int j=1;j<=mx;j++){ for(int p=0;p<1<<(11-i);p++){ for(int a=0;a<2;a++){ for(int b=0;b<2;b++){ f[j][p][a][b]=f[j-1][p][a][b]; if(j<=n) f[j][p][a][b]=(f[j-1][p^(j>>i)][a^(j>>i-1&1)][b]+f[j][p][a][b])%mod; if(j<=m) f[j][p][a][b]=(f[j-1][p^(j>>i)][a][b^(j>>i-1&1)]+f[j][p][a][b])%mod; } } } } (ans+=f[mx][0][0][1])%=mod; } return ans; } };