思路：
如果算上i=0&&j=0的情況，其實就是求[0,x][0,y]之間任意兩個整數中，滿足i&j=0的個數乘以log2(i+j)+1取下整數，因為資料范圍到了1e9并且測驗樣例1e5，所以聯想到對位進行操作，于是考慮到---數位dp，
數位dp: https://blog.csdn.net/m0_50623076/article/details/111564154
這個題模板題，賽場上沒有想到，賽場下后悔不已，
根據題意進行明確，i&j=0的情況，意味著相加不會進位，Log2(i+j)+1向下取整，意味著之和i、j中最長len值相等，
狀態：當前位數len,x的上限標記sx，y的上限標記sy，前導零zeros;
dp[len][sx][sy][zeros];
相較于模板，在這里不需要進行(!limit).那是為了防止高位限制導致后面出現高位不限制而多存在的情況，在這里我們直接讓它進入了dp中，也就是sx sy，
再者：ans注意判斷是否為最高位，因為這個不單單是統計個數，還有log2(i+j)+1！
代碼：(內含注釋)
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6+50;
int t;
int X,Y;
ll dp[35][2][2][2];//位數 x的狀態 y的狀態 之前是否一直為0
//dp[len][sx][sy][zeros]在長度為len，sx,sy限制、zeros是否為最高位的情況下符合情況的個數，
//回傳的是符合情況的結果(已×log(i+j)+1)，
ll x[35],y[35];
ll mod = 1e9+7;
//回傳的是對于長度為len的，sx sy對應 x y 高位限制的情況下，zeros是否前面全為零
//即這個len是最高位，有多少種情況符合，回傳的是符合情況的結果(已×log(i+j)+1)，
ll dfs(int len,int sx,int sy,int zeros){
//到了len=0也符合題意，這時候完成了一種情況 return 1；
if(len == -1) return 1;
//如果曾經記錄了這個情況dp，直接回傳，
if(dp[len][sx][sy][zeros] != -1) return dp[len][sx][sy][zeros];
//如果sx=0意味著前面有的數字有的取得并不是高位，這時候此位大多可取到1 sy同理，
int mx = (sx?x[len]:1);
int my = (sy?y[len]:1);
ll ans = 0;
//列舉位的情況
for(int i = 0;i <= mx;i++){
for(int j = 0;j <= my;j++){
if(i&j) continue;
int cnt = 1;
if(zeros&&(i||j)) cnt = len+1;
//如果前面全是0，此位出現1，證明為最高位 log(i+j)+1為len+1，
ans=(ans+dfs(len1,sx&&i==mx,sy&&j==my,zeros&&!i&&!j)*cnt%mod)%mod;
}
}
return dp[len][sx][sy][zeros] = ans;
}
ll solve(){
memset(dp,-1,sizeof(dp));
int len = 0;
while(X||Y){
x[len] = (X&1);
y[len] = (Y&1);
X>>=1;
Y>>=1;
len++;
}
//最高位為len-1位
return dfs(len-1,1,1,1);
}
int main(){
cin >> t;
while(t--){
cin >> X >>Y;
//i=0,j=0的情況洗掉，
cout << (solve()-1+mod)%mod <<endl;
}
return 0;
}
借鑒于：https://blog.csdn.net/weixin_44178736/article/details/111179926
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/239549.html
標籤：其他
上一篇：淺談路徑搜索問題