题面

题解

组合数

枚举有多少个\(1\),求出有多少种数

扫描\(n\)的每一位\(1\), 强制选\(0\)然后组合数算一下有多少种方案

Code

#include
    
     #define LL long long#define RG registerusing namespace std;template
     
       inline void read(T &x) {    x = 0; RG char c = getchar(); bool f = 0;    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();    x = f ? -x : x;    return ;}template
      
        inline void write(T x) {    if (!x) {putchar(48);return ;}    if (x < 0) x = -x, putchar('-');    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;}const int N = 55, Mod = 10000007;LL C[N][N], cnt, a[N];inline LL Pow(int a, LL b) {    LL s = 1;    for (LL x = a; b; b >>= 1, x = x*x%Mod) if (b&1) s = s*x%Mod;    return s;}int main() {    //freopen(".in", "r", stdin);    //freopen(".out", "w", stdout);    for (int i = 0; i <= 50; i++) C[i][i] = C[i][0] = 1;    for (int i = 2; i <= 50; i++)        for (int j = 1; j < i; j++)            C[i][j] = C[i-1][j-1]+C[i-1][j];    LL n; read(n);    for (int i = 50; i >= 0; i--) {        if ((n>>i)&1) {            for (int j = 1; j <= i; j++)                a[j+cnt] += C[i][j];//至少选1个的方案            a[++cnt]++;//不选的方案(必须分开算,不然会有重复计算)        }    }    LL ans = 1;    for (int i = 1; i <= 50; i++)        ans = ans*Pow(i, a[i])%Mod;    printf("%lld\n", ans);    return 0;}