这题我一开始就想到数位dp了，其实好像也不是很难，但是自己写不出来。。。常规套路，f[i][j][k][t],从后往前填数，i位，j代表是否卡着上沿，k是现在有几个1，t是想要有几个。记忆化搜索就ok啦！
题干：
题目背景 众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。 题目描述 话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的：设 sum(i) ext{sum}(i)sum(i) 表示 iii 的二进制表示中 111 的个数。给出一个正整数 NNN ，花神要问你 ∏i=1Nsum(i)prod_{i=1}^{N} ext{sum}(i)∏i=1Nsum(i) ，也就是 sum(1)∼sum(N) ext{sum}(1)sim ext{sum}(N)sum(1)∼sum(N) 的乘积。 输入输出格式 输入格式： 一个正整数 N。 输出格式： 一个数，答案模 10000007 的值。 输入输出样例 输入样例#1： 复制 3 输出样例#1： 复制 2 说明 对于 100% 的数据，N≤10^15
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;++i) #define lv(i,a,n) for(register int i = a;i >= n;--i) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 51; const int mod = 10000007; ll n; int x[N],cnt = 0; ll f[N][2][N][N]; ll ans[N]; ll qpow(ll a,ll b) { ll tot = 1; while(b) { if(b & 1) { tot *= a; tot %= mod; } a *= a; a %= mod; b >>= 1; } return tot; } ll _f(int cur,int up,int tmp,int d) { if(!cur) return tmp == d; if(~f[cur][up][tmp][d]) return f[cur][up][tmp][d]; int lim = up ? x[cur] : 1; ll ret = 0; for(int i = 0;i <= lim;++i) { ret += _f(cur - 1,up && i == lim,tmp + (i == 1),d); } return f[cur][up][tmp][d] = ret; } ll solve() { while(n) { x[++cnt] = n & 1; n >>= 1; } for(int i = 1;i <= 50;i++) { memset(f,-1,sizeof(f)); ans[i] = _f(cnt,1,0,i); } ll ret = 1; for(int i = 1;i <= 50;++i) { ret = ret * qpow(i,ans[i]) % mod; } } int main() { read(n); printf("%lld ",solve()); }