初见安~这里是两个传送门：洛谷P4317 & bzoj P3209
背景 众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。 描述 话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的 设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你 派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。
一个正整数 N。
一个数，答案模 10000007 的值。
对于样例一，1*1*2=2；
数据范围与约定
对于 100% 的数据，N≤10^15
对于我这种数位dp入门级别的选手来说这神仙就是个毒瘤题！！！！各大题解的思路我都很明白，但是具体的代码就是有些地方看不懂，也不给个注释QwQ……最后卡了一整天在牙牙姐的帮助下才终于搞明白了【实名感谢！！！】
进入正题。
题目意思很明显——求出1~n每个数的二进制下1的个数的乘积。如果我们按照1~n的固定思路来思考，那么除了暴力累乘你也没有别的出路了。如果打乱了来看呢？有没有发现只要是位数<n的数，按位数放在一起就是一个组合数？那我们就按位数的思路来思考吧【本来就是个数位dp你不考虑位数你咋整！！】我们设f[ i ] [ j ] 为以0开头的一个i位数有j个1的情况数量，g[ i ] [ j ]为保证第一位为1的情况下i位数有j个1的情况数量。很明显我们可以根据定义得到一个递推式：【加进来的数可以是0】这里其实f和g的定义都差不多，推导方式也都比较灵活，甚至可以只开f，开两个是为了某些细节处理方便。同时g也可以得出一个递推式：
然后我们要考虑从高位到低位地利用f。从低位开始可能不太好处理大小限制。【其实只有0和1的话还是很好处理的】处理出每一段可以得到多少种情况，然后累乘快速幂就行了【这是最大的思路，下面详解】
我们举个例子：1100101这个数【已经是二进制状态】
如果最高位为0，那么后面的6位就可以是一个在6个空位里放1~6个1的排列组合，得出所有满足要求的6位数。那么如果最高位取1呢？是不是就很明显受到后面的数的限制了很麻烦？那我们就从后面的数的角度来处理这个1就好。什么意思——我们在最开始处理这个7位数时，是假设当前位——第七位——为0，就可以合法快速幂出后面的6位的全排列【0111111 < 1100101】。如果我们继续往后走，到第六位，明显我们再直接假设这一位是0就会重复一些前面7位时枚举过的情况，所以前面的第七位我们要固定为1了。这样一来就是形如10……，有5位我们在枚举情况，但是最多可以有6个1，因为第七位的1已经固定，随意的是后面的几个。同理往后推，遇到1就处理然后固定………………
可能你有个疑问——为什么在枚举这一步中调用的是f而不是g？实质上我们在枚举的时候就很明显——首先开头的那个数是一定可以为0的。其次，f其实虽然定义上是以0开头，但是我们在递推的时候到了i == j的时候还是会正常算出以1开头的全是1的数的情况，也因为递推的时候一定不会用到这个末端的情况所以完全不影响。所以f其实是很灵活的，也正好适合这个灵活的枚举过程。
真的是巧妙极了呢。下面是代码及详解——
#include<bits/stdc++.h> #define ll long long #define int ll//这个纯属是我不知道哪里错了所以乱搞。 using namespace std; ll f[100][100], g[100][100];// f 0 g 1 ll n, p = 10000007; ll pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans; } ll cal(ll x) { ll t = 0, c = 0, ans = 1;//t为剩下的可处理位数，c为已经固定了的1的数量 while(1ll << t <= x) t++;//统计x除了最高位的位数 for( ; t; t--) { if((1ll << t - 1) & x)//x的第t位上为1，就可以拆出来 { for(int i = 1; i <= t; i++) ans = ans * pow(i + c, f[t][i]) % p;//有i + c个1，但是真正可以活动的只有i个 if(c) ans = ans * c % p;//十分巧妙的细节处理，较难理解，其实算的时候最高位一直是0 c++;//这一位为1，c要累加 } } return ans * c % p; } signed main()//就是int main（） { scanf("%lld", &n); f[1][0] = 1, g[1][1] = 1; for(int i = 2; i <= 60; i++) for(int j = 0; j <= i; j++)//预处理出f和g { f[i][j] = f[i - 1][j] + g[i - 1][j]; if(j) g[i][j] = g[i - 1][j - 1] + f[i - 1][j - 1]; } printf("%lld", cal(n)); return 0; }真的是个毒瘤题啊。
迎评：） ——End——
