233

题目：题意：分析：代码：

---

题目：

传送门

---

题意：

给出一个正整数$n$ ，问你 ${\prod }_{i=1}^{N}sum(i)$ $p.s.sum(i)$为$i$在二进制下时$1$的个数

---

分析：

对于数$n$来说，必定是$1—n$中最大的这不废话吗 因此，可以有两个引理： $1.$在二进制下$ta$的首位$1$一定是出现最早的 $2.$首位$1$出现的位置后都必定存在$1$ 证明： $1.$因为$n$是最大的，所以显然(逃 $2.$假设$n$为$4$,，则在二进制下为$1000$，因为我们要求的是$1—n$。所以必定存在一个恰好比$n$少一位并且所有位上的都是$1$，我们成为$super$ $number$。在这个例子中，$supernumber$是$3$，即$111$ 根据$引理1$，我们得到了需要倒序求解的思路 $(n_2表示$n$的二进制数)$ 根据$引理2$，我们知道的当$n_2$出现$1$后，之后便可以直接累加 用人话来说，设$f_i$为$1$出现次数恰好为$i$时的方案数(雾不知道怎么正确表达) 随后我们可以得到一个式子： $$\sum _{i=n}^{1}f[i]+=f[i-1](其实不需要\sum ，只是觉得这样表示循环比较高级233)$$ 也就是上文说到的累加，当我们遍历多一位时，$1$出现的次数便必然会$+1$ $P.S.$因为我们不能保证$n$一定是$supernumber$，所以统计$1$出现的次数时从$0$开始统计，最后再补上一次便不会漏记，且因为我们补得是最后一位，所以不用再进行累加

---

代码：

// luogu-judger-enable-o2 #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define LL long long #define LZX 10000007 inline LL read() { LL d=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();} return d*f; } using namespace std; LL ksm(LL x,LL y) { LL s=1; while(y) { if(y%2) (s*=x)%=LZX; y/=2;(x*=x)%=LZX; } return s; } LL f[55],cnt=0; int main() { LL n=read(); for(LL j=49;~j;j--) { for(LL i=49;i;i--) f[i]+=f[i-1]; if(n>>j&1) f[cnt++]++; } f[cnt]++; LL ans=1; for(LL i=1;i<=49;i++) (ans*=ksm(i,f[i]))%=LZX; cout<<ans; return 0; }