题解：CF1957E Carousel of Combinations

Pengzt · 2025-01-13 12:08:05 · 题解

Carousel of Combinations

题目链接。cnblogs。

Problem

求：\sum\limits_{i=1}^n\sum\limits_{j=1}^i\left(F(i,j)\bmod j\right)。

其中 F(i,j) 表示从 i 个数当中选 j 个的不同圆排列数。

最终答案对 10^9+7 取模。

注意区分题目中的两个取模的位置。

数据范围：t \le 10^5，n \le 10^6。

Sol

首先 F(i, j) = \frac{i!}{(i - j)!j} = \binom ij (j - 1)!。然后 (j - 1)! \bmod j 只有在 j 是素数或者 j=4 的时候值不为 0。j = 4 的时候可以单独算。当 j \in \text{prime} 的时候，F(i, j) = -\binom ij \bmod j = -\binom{\lfloor i/j \rfloor}{j/j}\times \binom{i \bmod j}{j \bmod j} = -\lfloor \frac ij \rfloor。现在要求 \sum\limits_{p \in \text{prime}} ((\sum\limits_{i = 1}^{n} \lfloor \frac{i}{p} \rfloor) \bmod p)。这个东西直接做是会 T 的，但是 \lfloor \frac ip \rfloor 的总的断点个数是 \mathcal{O}(n \ln \ln n) 的。考虑对这个东西直接线性筛，枚举质数 p，然后就是做 \lfloor \frac np \rfloor 段区间加。这里可以直接差分，最后跑一遍前缀和即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
int vis[1000005], prC, pri[1000005];
ll ans[1000005];
void Init(int n = 1e6) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) pri[++prC] = i;
        for (int j = 1; j <= prC && i * pri[j] <= n; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
    vis[4] = 0;
    for (int i = 2; i <= n; ++i) {
        if (vis[i]) continue;
        ll t = i == 4 ? 2 : i - 1;
        for (int j = 1, k = i; k <= n; ++j, k += i) {
            ll w = j * t % i;
            (ans[k] += w) %= mod;
            if (k + i <= n) (ans[k + i] -= w) %= mod;
        }
    }
    for (int i = 1; i <= n; ++i) (ans[i] += ans[i - 1] + mod) %= mod;
    for (int i = 1; i <= n; ++i) (ans[i] += ans[i - 1] + mod) %= mod;
}
int n;
void Solve() {
    scanf("%d", &n);
    printf("%lld\n", ans[n]);
}
int main() {
    Init();
    int T;
    scanf("%d", &T);
    while (T--)
        Solve();
    return 0;
}