「Luogu4317」花神的数论题

思维僵化不会写题了QAQ

problem

题目背景

众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
题目描述

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设 sum(i)sum(i) 表示 ii 的二进制表示中 11 的个数。给出一个正整数 NN ，花神要问你 ∏i=1Nsum(i)\prod_{i=1}^Nsum(i) ，也就是sum(1)∼sum(N)sum(1)∼sum(N)的乘积。

输入输出格式

输入格式：

一个正整数 NN。

输出格式：

一个数，答案模 1000000710000007 的值。

输入输出样例

输入样例#1：

1
3

输出样例#1：

1
2

说明

对于 100100% 的数据，N≤1015N≤10^{15}

Solution I

位数计算显然可以用数位DP来搞

有一位神仙曾经说过

当你不会写DP的时候，你就可以先写一个暴搜，然后再改成记搜 ——神仙

一语点醒梦中人，如雷贯耳（雾）

于是我们考虑按位数从高到低暴搜，并且记录11的个数。
特别地，我们令sum(0)=1sum(0)=1

然后加上记忆化就完事了

Code

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define maxb 69
using namespace std;
typedef long long ll;

const ll mod=10000007;
ll n;
ll lim[maxb],len;
ll dp[maxb][maxb];

ll Search(ll pos,ll cnt,bool limit)
{
    if(!pos)return max(cnt,1LL);
    if(~dp[pos][cnt] && !limit)return dp[pos][cnt];
    ll re=1;
    for(register ll i=0;i<=(limit?lim[pos]:1);++i)
        re=re*Search(pos-1,cnt+i,limit&&(i==lim[pos]))%mod;
    if(!limit)dp[pos][cnt]=re;
    return re;
}

int main()
{
    scanf("%lld",&n);
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        lim[++len]=n&1;
        n>>=1;
    }
    printf("%lld",Search(len,0,1));
    return 0;
}

Solution II

我们可以换个思路

我们可以通过数位DP求出在[1,N][1,N]的所有数中,二进制下11的个数为1,2,3,…,len1,2,3,\dots,len的数的个数

然后使用快速幂即可求出答案

于是dp[i][j]dp[i][j]表示枚举到第ii位，前ii位已经有jj个11的答案个数

然后可以愉快地套模板辣

Code

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
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define maxb 69
using namespace std;
typedef long long ll;

const ll mod=10000007;
ll n;
ll lim[maxb],len;
ll dp[maxb][maxb],cnts[maxb],ans=1;

ll Search(ll cur,ll pos,ll cnt,bool limit)
{
	if(!pos)return cnt==cur;
	if(~dp[pos][cnt] && !limit)return dp[pos][cnt];
	ll re=0;
	for(register ll i=0;i<=(limit?lim[pos]:1);++i)
		re+=Search(cur,pos-1,cnt+i,limit&&(i==lim[pos]));
	if(!limit)dp[pos][cnt]=re;
	return re;
}

ll fastpow(ll a,ll b)
{
	ll re=1,base=a;
	while(b)
	{
		if(b&1)re=re*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return re;
}

int main()
{
	scanf("%lld",&n);
	while(n)
	{
		lim[++len]=n&1;
		n>>=1;
	}
	for(register ll i=1;i<=len;++i)
	{
		memset(dp,-1,sizeof(dp));
		cnts[i]=Search(i,len,0,1);
//		cerr<<cnts[i]<<" ";
	}
	for(register int i=1;i<=len;++i)
		ans=ans*fastpow(i,cnts[i])%mod;
	printf("%lld",ans);
	return 0;
}