TopCoder SRM 595 Div2 第3題

類型：數論  難度：2.5

題意：給出三個數A,B,C，求（X,Y）的數目，（X,Y）滿足 0 <= X <= A, 0 <= Y <= B，且（X異或Y）<=C

分析：最近碰到很多計數題，這題花了不少時間，方法有點麻煩。。

先将A，B，C轉換為二進制存入數組，dp[pos][ia][ib][ic]表示第pos位A，B，C是否置定，ia,ib,ic為0,1，0表示未置定，1表示置定。

ia置定即該位A可任取0,1，置定的原因是：A[k]=1，而實際取0，其中k>pos。即比pos高的位上A實際為1，但是取了0，故A後邊的位可随意取值，稱為置定。

給出這個概念後，分情況寫出狀态轉移方程，讨論ia,ib,ic的所有取值組合（000-111）8種情況，每種情況中，當ia,ib,ic為0時，還要讨論A[pos],B[pos],C[pos]的取值，分别寫方程。

代碼如下：

#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;

const int maxM = 40;

class LittleElephantAndXor
{ 
	int a[maxM],b[maxM],c[maxM];
	long long dp[maxM][2][2][2];
	 
	public:
		void intToBit(int arr[],int n)
		{
			for(int i=0; n; i++,n>>=1)
			{
				arr[i] = n&1;
			}
		}
		
		long long mypow(long long x,int y)
		{
			long long ans = 1;
			while(y--) ans *= x;
			return ans;
		}
		
		long long fun(int pos,bool ia,bool ib,bool ic)
		{
			//printf("%d %d %d %d\n",pos,ia,ib,ic);
			if(pos < 0) return 1;
			if(dp[pos][ia][ib][ic] >= 0) return dp[pos][ia][ib][ic];
			
			long long ans,two = 2;
			if(ia && ib && ic)
				ans = mypow(two,two*(pos+1));
			else if(ia && ib)
			{
				if(c[pos]) ans = two*(fun(pos-1,1,1,0)+fun(pos-1,1,1,1));
				else ans = two*fun(pos-1,1,1,0);
			}
			else if(ia && ic)
			{
				if(b[pos]) ans = two*(fun(pos-1,1,0,1)+fun(pos-1,1,1,1));
				else ans = two*fun(pos-1,1,0,1);
			}
			else if(ib && ic)
			{
				if(a[pos]) ans = two*(fun(pos-1,0,1,1)+fun(pos-1,1,1,1));
				else ans = two*fun(pos-1,0,1,1);
			}
			else if(ia)
			{
				if(b[pos])
				{
					if(c[pos]) ans = fun(pos-1,1,0,0) + fun(pos-1,1,1,0) + fun(pos-1,1,0,1) + fun(pos-1,1,1,1);
					else ans = fun(pos-1,1,0,0) + fun(pos-1,1,1,0);
				}
				else
				{
					if(c[pos]) ans = fun(pos-1,1,0,0) + fun(pos-1,1,0,1);
					else ans = fun(pos-1,1,0,0);
				}
			}
			else if(ib)
			{
				if(a[pos])
				{
					if(c[pos]) ans = fun(pos-1,0,1,0) + fun(pos-1,1,1,0) + fun(pos-1,0,1,1) + fun(pos-1,1,1,1);
					else ans = fun(pos-1,0,1,0) + fun(pos-1,1,1,0);
				}
				else
				{
					if(c[pos]) ans = fun(pos-1,0,1,0) + fun(pos-1,0,1,1);
					else ans = fun(pos-1,0,1,0);
				}
			}
			else if(ic)
			{
				if(a[pos])
				{
					if(b[pos]) ans = fun(pos-1,0,1,1) + fun(pos-1,1,1,1) + fun(pos-1,1,0,1) + fun(pos-1,0,0,1);
					else ans = fun(pos-1,0,0,1) + fun(pos-1,1,0,1);
				}
				else
				{
					if(b[pos]) ans = fun(pos-1,0,0,1) + fun(pos-1,0,1,1);
					else ans = fun(pos-1,0,0,1);
				}
			}
			else
			{
				if(a[pos])
				{
					if(b[pos])
					{
						if(c[pos]) ans = fun(pos-1,0,0,1) + fun(pos-1,1,1,1) + fun(pos-1,1,0,0) + fun(pos-1,0,1,0);
						else ans = fun(pos-1,0,0,0) + fun(pos-1,1,1,0);
					}
					else
					{
						if(c[pos]) ans = fun(pos-1,1,0,1) + fun(pos-1,0,0,0);
						else ans = fun(pos-1,1,0,0);
					}
				}
				else
				{
					if(b[pos])
					{
						if(c[pos]) ans = fun(pos-1,0,0,0) + fun(pos-1,0,1,1);
						else ans = fun(pos-1,0,1,0);
					}
					else
					{
						if(c[pos]) ans = fun(pos-1,0,0,1);
						else ans = fun(pos-1,0,0,0);
					}
				}
			}
			dp[pos][ia][ib][ic] = ans;
			//printf("%d %d %d %d %lld\n",pos,ia,ib,ic,dp[pos][ia][ib][ic]);
			return dp[pos][ia][ib][ic];
		}
		
		long long getNumber(int A, int B, int C)
		{
			memset(a,0,sizeof(a));
			memset(b,0,sizeof(b));
			memset(c,0,sizeof(c));
			intToBit(a,A);
			intToBit(b,B);
			intToBit(c,C);
			
			memset(dp,-1,sizeof(dp));
			return fun(maxM-1,0,0,0);
		}
};

int main()
{
	LittleElephantAndXor t; 
	cout<<t.getNumber(5e8,2e8,1)<<endl;
}