BZOJ 3209 花神的數論題 數位DP+數論

BZOJ 3209 花神的數論題 數位DP+數論

題目大意：令Sum(i)為i在二進制下1的個數 求∏(1<=i<=n)Sum(i)

一道很簡單的數位DP 首先我們打表打出組合數 然後利用數位DP統計出二進制下1的個數為x的數的數量 最後輸出∏(1<=x<=logn)x^ans[x]即可

此題的坑在於這題的組合數和數位DP的結果都是指數 對指數取模不能直接取 要取Phi(p)

於是我們對10000006取模 然後這題就WA了 因為10000007不是個質數！

10000007=941*10627 於是我們得到Phi(p)=940*10626=9988440 對這個數取模即可

其實不取模就可以，一定不會爆long long的。。。我是何必呢這是。。。

#include
#include
#include
#include
#define M 10000007
#define Phi_M 9988440
using namespace std;
typedef long long ll;
ll n,f[60][60],ans[60],output=1;
void Digital_DP(ll x)
{
	int i,j,cnt=0;
	ll now=0;
	for(i=1;1ll<>=1;
	}
	return re;
}
int main()
{
	int i,j;
	for(i=0;i<=55;i++)
	{
		f[i][0]=1;
		for(j=1;j<=i;j++)
			f[i][j]=(f[i-1][j]+f[i-1][j-1])%Phi_M;
	}
	cin>>n;
	Digital_DP(n+1);
	for(i=1;i<=55;i++)
		output*=Quick_Power(i,ans[i]),output%=M;
	cout<