CF1957E Carousel of Combinations

思路

首先先把原式中的 $C(i,k)$ 化出来：

$$C(i,j) \bmod j = \frac{A^i_j}{j} \bmod j = \frac{i(i - 1)\cdots(i - j + 1)}{j} \bmod j = ((j - 1)! \times \lfloor \frac{i}{j} \rfloor) \bmod j$$

由威尔逊定理，当 $p$ 为质数时：

$$(p - 1)! \bmod p = p - 1$$

其次当 $p$ 为非质数时，$p = 4$ 结果为 $2$；其余情况为 $0$。

定义 $dp_i = \sum_{j = 1}^{i}{((j - 1)! \times \lfloor \frac{i}{j} \rfloor \bmod j)}$。最后结果就是 $\sum_{i = 1}^{n}{dp_n}$。

考虑类似埃筛的处理，考虑每一个 $j$ 对于每一个 $dp_i$ 的贡献。发现在 $i \in [k \times j,(k + 1) \times j)$ 时，会为每一个 $dp_i$ 贡献同一个值：$(j - 1)! \times \lfloor \frac{i}{j} \rfloor \bmod j$。

然后区间修改，直接差分维护即可。

注意特判 $4$。

Code

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) % mod + (b) % mod) % mod)
#define Sub(a,b) ((((a) % mod - (b) % mod) % mod + mod) % mod)

using namespace std;

const int N = 1e6 + 10,mod = 1e9 + 7;
int dp[N];
bool vis[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void init(){
    for (re int i = 2;i <= 1e6;i++){
        if (!vis[i] || i == 4){
            for (re int j = i;j <= 1e6;j += i){
                vis[j] = true;
                int val = j / i;
                if (i == 4) val *= 2;
                else val *= (i - 1);
                val %= i;
                dp[j] = Add(dp[j],val);
                if (i + j <= 1e6) dp[i + j] = Sub(dp[i + j],val);
            }
        }
    }
    for (re int i = 1;i <= 1e6;i++) dp[i] = Add(dp[i - 1],dp[i]);
    for (re int i = 1;i <= 1e6;i++) dp[i] = Add(dp[i - 1],dp[i]);
}

signed main(){
    init();
    int T; T = read();
    while (T--) printf("%lld\n",dp[read()]);
    return 0;
}