題目鏈接：點擊查看
題目大意：給出?X 和 Y，求?
題目分析：因為涉及到了位運算且看似可以遞推，所以考慮數位dp，因為統計答案時的 i 和 j 的與為 0，所以 i + j = i & j，那么取 log 其實就是最高位，也就是 max( highbit_i , highbit_j )
最簡單的狀態就是：dp[ pos ][ highbit_x ][ highbit_y ][ x <= X ][ y <= Y ]，不過很可惜會 TLE
因為我們到達終點后，我們只關心 max( highbit_x , highbit_y )，所以狀態優化為?dp[ pos ][ max( highbit_x , highbit_y ) ][ x <= X ][ y <= Y ]，很可惜還是會 TLE
然后就沒思路了，去看了題解恍然大悟，其實我們可以去枚舉最高位的，假設 i 為最高位，也就是?max( highbit_x , highbit_y ) 為 i，此時只有兩種情況：
x 和 y 大于 i 的位置全為 0，x 的 i 為 1，y 的 i 為 0x 和 y 大于 i 的位置全為 0，x 的 i 為 0，y 的 i 為 1
每次都去數位 dp 即可，時間復雜度下降到了最終的 O( 2 * 35 * 2 * 2 ) ≈ O( 280 )
最后再補充一下，dp 數組記憶化的實質上是當前狀態下有多少個 i & j == 0，最后的貢獻還是需要乘上相應的 highbit + 1
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int mod=1e9+7;LL dp[35][2][2];//dp[pos][i<=x][j<=y]int A[35],B[35];LL dfs(int pos,int f1,int f2)
{if(pos==-1)return 1;if(dp[pos][f1][f2]!=-1)return dp[pos][f1][f2];int upa=f1?A[pos]:1;int upb=f2?B[pos]:1;LL ans=0;for(int i=0;i<=upa;i++)//枚舉A for(int j=0;j<=upb;j++)//枚舉Bif((i&j)==0)ans=(ans+dfs(pos-1,f1&&i==upa,f2&&j==upb))%mod;return dp[pos][f1][f2]=ans;
}LL solve(int x,int y)
{memset(A,0,sizeof(A));memset(B,0,sizeof(B));memset(dp,-1,sizeof(dp));int cnt1=0,cnt2=0;//highbitint xx=x,yy=y;while(xx){A[cnt1++]=xx&1;xx>>=1;}while(yy){B[cnt2++]=yy&1;yy>>=1;}LL ans=0;for(int i=0;i<max(cnt1,cnt2);i++){LL res=0;if(i<cnt1)//第i位x為1,y為0 res+=dfs(i-1,i==cnt1-1,i>=cnt2);if(i<cnt2)//第i為y為1,x為0 res+=dfs(i-1,i>=cnt1,i==cnt2-1);ans=(ans+res*(i+1))%mod;}return ans;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){int x,y;scanf("%d%d",&x,&y);printf("%lld\n",solve(x,y));}return 0;
}
?
總結
以上是生活随笔為你收集整理的2020ICPC(上海) - Sum of Log(数位dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
