[SRM603] WinterAndSnowmen

Description

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;
    }
};