BZOJ 3209 花神的数论题

明明和数论基本上没有关系好伐……
题面严重误导（大雾）。

题目要求的是 N∏i=1sum(i)，但是如果我们 O(N) 计算显然会超时对吧。
发现 [1,N] 中 sum(i) 的取值只有 log2N≈50 种。
于是我们考虑把相同的 sum(i) 放到一起乘，就可以快速幂。

所以就枚举 sum(i) 的取值然后数位 DP 统计即可。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 50;
const long long mod = 1e7 + 7;
long long n;
int d[LEN + 5],tot;
long long f[LEN + 5][LEN + 5];
long long ans = 1;
long long dfs(int x,int cnt,int top)
{
    if(cnt < 0)
        return 0;
    if(!x)
        return cnt == 0;
    if(!top && ~f[x][cnt])
        return f[x][cnt];
    int bound = top ? d[x] : 1;
    long long ret = 0;
    for(register int i = 0;i <= bound;++i)
        ret += dfs(x - 1,cnt - i,top && i == bound);
    if(!top)
        f[x][cnt] = ret;
    return ret;
}
long long fpow(long long a,long long b)
{
    long long ret = 1;
    while(b)
    {
        if(b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%lld",&n);
    while(n)
        d[++tot] = n & 1,n >>= 1;
    for(register int i = 1;i <= tot;++i)
        ans = ans * fpow(i,dfs(tot,i,1)) % mod;
    printf("%lld\n",ans);
}