BZOJ 3209 花神的数论题

发表于 | 分类于 |

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

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

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

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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);
}