【题解】10.31模拟赛T3：青青草原的表彰大会

solution

所有工资最多有$lo{g}_2^n$个不同的数，设个数为$d$ 令不同的数为{$p_i$},$p_1,p_2,...,p_d$ $d{p}_{i,j}$表示长度为$i$，$p_i=j$的$p$数列个数 转移方程$$d{p}_{i+1,j\ast l}+=d{p}_{i,j}$$ 令$$cn{t}_i=\sum _{j=1}^{n}d{p}_{i,j}$$ 得到$$ans=\sum _{i=1}^{lo{g}_2^n}cn{t}_i\ast C_{k-1}^{i-1}$$

Code：

#include <bits/stdc++.h> #define maxn 1000010 #define LL long long using namespace std; const LL qy = 1000000007; const int m = 22; int n, k; LL fac[maxn], inv[maxn], cnt[30], dp[23][maxn]; LL ksm(LL n, LL k){ if (!k) return 1; LL sum = ksm(n, k >> 1); sum = sum * sum % qy; if (k & 1) sum = sum * n % qy; return sum; } LL C(int n, int m){ return fac[n] * inv[n - m] % qy * inv[m] % qy; } int main(){ freopen("commend.in", "r", stdin); freopen("commend.out", "w", stdout); scanf("%d%d", &n, &k); fac[0] = 1; for (int i = 1; i < maxn; ++i) fac[i] = fac[i - 1] * i % qy; inv[maxn - 1] = ksm(fac[maxn - 1], qy - 2); for (int i = maxn - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % qy; for (int i = 1; i <= n; ++i) dp[1][i] = 1; for (int i = 1; i < m; ++i) for (int j = 1; j <= n; ++j) for (int l = j << 1; l <= n; l += j) (dp[i + 1][l] += dp[i][j]) %= qy; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) (cnt[i] += dp[i][j]) %= qy; LL ans = 0; for (int i = 1; i <= m && i <= k; ++i) (ans += cnt[i] * C(k - 1, i - 1) % qy) %= qy; printf("%lld\n", ans); return 0; }