专栏文章

题解：CF1957E Carousel of Combinations

PPengzt
CF1957E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqj16jo
此快照首次捕获于
2025/12/04 05:36
3 个月前
此快照最后确认于
2025/12/04 05:36
3 个月前
查看原文

Carousel of Combinations

题目链接。cnblogs。

Problem

求：∑i=1n∑j=1i(F(i,j) mod j)\sum\limits_{i=1}^n\sum\limits_{j=1}^i\left(F(i,j)\bmod j\right)。
其中 F(i,j)F(i,j) 表示从 ii 个数当中选 jj 个的不同圆排列数。
最终答案对 109+710^9+7 取模。
注意区分题目中的两个取模的位置。
数据范围：t≤105t \le 10^5，n≤106n \le 10^6。

Sol

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

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...