Luogu P4317 花神的数论题

Luogu P4317 花神的数论题

发现有大量 (sum(i)) 是相等的，并且其范围仅为 $left[ 0 , log_2^n right)，于是想求出其指数然后直接快速幂。

所以我们要求的是 (N) 中二进制表示下有 (m) 个 (1) 的个数，直接数位DP

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=100;
const int mod=1e7+7;
int m,a[N],s;
ll f[N][N],
n,ans;
ll power(ll x,ll n){
	ll a=1;
	while(n){
		if(n&1)a=a*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return a;
}
void solve(){
	for(ll i=n;i;i>>=1)a[++m]=i&1;
	f[m][0]=s=1;
	fd(i,m-1,1){
		fo(j,0,m-i){
			f[i][j]+=f[i+1][j];
			f[i][j+1]+=f[i+1][j];
		}
		if(a[i]){
			++f[i][s];
			++s;
		}
	}
	++f[1][s];
	ans=1;
	fo(i,1,m){
		ans=ans * power(i,f[1][i]) % mod;
	}
}
int main(){
	scanf("%lld",&n);
	solve();
	printf("%lld
",ans);
	
	return 0;
}