题目大意:令Sum(i)为i在二进制下1的个数 求∏(1<=i<=n)Sum(i)
一道非常easy的数位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 9988440using 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< <=x;i++); for(;~i;i--) if(now+(1ll< <=x) { for(j=0;j<=i;j++) ans[j+cnt]=(ans[j+cnt]+f[i][j])%Phi_M; ++cnt; now+=(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<