P4317 花神的数论题

着重考虑下$sum(i)$这个东西,二进制数表示情况下1的数量,如果限定的是位数而不是$N$的话可以去考虑搞一下组合数学.
$sum(i)$的数量太多了,考虑下分组来计算
$f(i):有f(i)个数字,对应的sum值是i$
$ans=\prod i^{f(i)}$
然而想了半天似乎并不会求这个东西,学了一天数位dp后回来写这个题
我去,和我想象的又不太一样,第一题写的是十进制意义下的一个题目,这个题是二进制的
学成归来，运用下数位dp的思路考虑下这个问题.
快有好几天没写,回顾下要做的东西:
需要求解一个函数$f(i):i个1出现的次数$
状态设置为$dp(cur,num,top)$,在选第$cur$个数字,已经选了$num$个1,是否贴着上界$top$
然而这个题最大的坑点是:你$dfs$算出来的是一个指数,指数是不能取模的,就像快速幂里面$pw(a,b)$
$取模是只能对底数取模,因为a^{b\%mod}!=a^b\%mod$
然后$dfs$过程不要取模就可以了

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 50+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
ll dp[maxn][maxn][2];
int a[maxn];ll f[maxn];
ll mod = 1e7+7;
ll dfs(int cur,int num,bool top,int limit){
	if(cur==0){
		if(num==limit) return 1;
		return 0;
	}
	ll &ans = dp[cur][num][top];
	if(ans!=-1) return ans;
	ans = 0;
	int bound = top?a[cur]:1;
	for(int i=0;i<=bound;i++){
//		if(i==1&&num==limit) continue;
		ans+=dfs(cur-1,num+i,top&&(i==bound),limit); 
	}
	return ans;
}
void solve(ll n){
	int len = 0;
	while(n) a[++len] = n&1,n>>=1;
	for(int i=1;i<=50;i++){
		memset(dp,-1,sizeof(dp));
		f[i] = dfs(len,0,1,i);
	}
}
ll pw(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans = ans*a%mod;
		b>>=1;a = a*a%mod;
	}
	return ans%mod;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;cin>>n;
	solve(n);
	ll ans = 1;
	for(int i=1;i<=50;i++){
		ans = ans * pw(i,f[i])%mod;
	}
	cout<<ans<<"\n";
}

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
59
60
61
62