2020ICPC(上海) - Sum of Log(數位dp)-有解無憂

題目鏈接：點擊查看

題目大意：給出 X 和 Y，求 $\sum_{i=0}^{X} \sum_{j=[i=0]}^{Y}[i\&j=0]\left \lfloor log_2(i+j)+1 \right \rfloor$

題目分析：因為涉及到了位運算且看似可以遞推，所以考慮數位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 為 0
x 和 y 大于 i 的位置全為 0，x 的 i 為 0，y 的 i 為 1

每次都去數位 dp 即可，時間復雜度下降到了最終的 O( 2 * 35 * 2 * 2 ) ≈ O( 280 )

最后再補充一下，dp 陣列記憶化的實質上是當前狀態下有多少個 i & j ，最后的貢獻還是需要乘上相應的 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++)//列舉B
			if((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;//highbit
	int 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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/234961.html

標籤：其他

上一篇：一文決議App推廣神器deeplink(深度鏈接)

下一篇：游戲開發中的插補