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);
}