题解 E. NTT 集美大学第九届程序设计竞赛

传送门

现场没推出了，找了个规律，发现是 \((n+1)^{n-1}\) 就直接冲过了

【分析】

考虑 \(0\leq k<n\) ，所以 \(\min(k, n-1)=k\)

因此有：
\(\begin{aligned} &\sum_{i=k}^{\min(k, n-1)+n-1}{\text{lcm}(i-k+1, n)\over k+1} \\=&\sum_{i=1}^n {\text{lcm}(i, n)\over k+1} \\=&{1\over k+1}\sum_{i=1}^n{in\over \gcd(i, n)} \\=&{1\over k+1}\cdot n\cdot\sum_{g\mid n}{1\over g}\sum_{i=1}^n[\gcd(i, n)=g]i \\=&{n\over k+1}\cdot \sum_{g\mid n}\sum_{i=1}^{n\over g}[\gcd(i, {n\over g})=1]i \end{aligned} \)
而其中，不超过 \(x\) 的与 \(x\) 互质的数和，是经典题目，有：
\(\begin{aligned} s(m)&=&\sum_{i=1}^m [\gcd(i, m)=1]i \\&=&\sum_{d\mid m}\boldsymbol \mu(d)\sum_{i=1}^m[d\mid i]i \\&=&\sum_{d\mid m}\boldsymbol \mu(d)\cdot d\cdot {{m\over d}\cdot ({m\over d}+1)\over 2} \\&=&{m\over 2}(\sum_{d\mid m}\boldsymbol \mu(d)\cdot {m\over d}+\sum_{d\mid m}\boldsymbol \mu(d)) \\&=&{m\over 2}\cdot (\boldsymbol \varphi(m)+[m=1]) \end{aligned} \)
于是给定式子化简为 \(\displaystyle {1\over k+1}\cdot n\cdot \sum_{g\mid n} s(g)\) 。除了 \(\displaystyle {1\over k+1}\) 显然可以通过枚举倍数的方法，在 \(\displaystyle O(\sum_{i=1}^n{n\over i})=O(n\log n)\) 的时间内预处理

剩余的部分考虑组合意义：

\(n\) 种字符中，有 \(k\) 个从未使用，构成长度为 \(n\) 的字符串方案数

等价于从 \(n\) 个互不相同的盒子中选择 \(n-k\) 个，然后将 \(n\) 个小球放入这 \(n-k\) 个互不相同的盒子，要求每个选定的盒子非空，问方案数

考虑第二类斯特林数的组合意义，不难写出公式 \(\displaystyle \dbinom {n} {n-k}\cdot \begin{Bmatrix}n\\n-k\end{Bmatrix}\cdot (n-k)!\)

于是答案为：
\(\begin{aligned} &\sum_{k=0}^{n-1}\dbinom {n} {n-k}\cdot \begin{Bmatrix}n\\n-k\end{Bmatrix}\cdot (n-k)!\cdot {1\over k+1}\cdot n\cdot \sum_{g\mid n}s(g) \\=&(\sum_{k=1}^n\dbinom {n} {k}\cdot \begin{Bmatrix}n\\k\end{Bmatrix}\cdot k!\cdot {1\over n-k+1})\cdot (n\cdot \sum_{g\mid n}s(g)) \\=&(\sum_{k=0}^{n-1}{n!\over (n-k)!}\cdot \begin{Bmatrix}n\\k+1\end{Bmatrix})\cdot (n\cdot \sum_{g\mid n}s(g)) \end{aligned} \)
考虑第二类斯特林数和下降幂的关系有：
\(\begin{aligned} &\sum_{k=0}^{n-1}{n!\over (n-k)!}\cdot \begin{Bmatrix}n\\k+1\end{Bmatrix} \\=&{1\over n+1}\sum_{k=1}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}(n+1)^{\underline k} \\=&{1\over n+1}\cdot [(n+1)^n-\begin{Bmatrix}n\\0\end{Bmatrix}] \\=&(n+1)^{n-1}&(n>0) \end{aligned}\)

于是直接冲就完事了

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=998244353;
inline int kpow(int a, int x, int p=P) { int ans=1; for(; x; x>>=1, a=(ll)a*a%p) if(x&1) ans=(ll)ans*a%p; return ans; }
inline int inv(int a, int p=P) { return kpow(a, p-2, p); }
const int Lim=1e6, MAXN=Lim+10;
int n, phi[MAXN], f[MAXN];
int prime[MAXN], cntprime, fc[MAXN];
inline void init() {
	phi[1]=1;
	for(int i=2; i<=Lim; ++i) {
		if(!fc[i]) fc[i]=prime[++cntprime]=i, phi[i]=i-1;
		for(int j=1; j<=cntprime; ++j)
			if(prime[j]>fc[i]||prime[j]*i>Lim) break;
			else {
				fc[prime[j]*i]=prime[j];
				phi[prime[j]*i]=(fc[i]==prime[j]?prime[j]:prime[j]-1)*phi[i];
			}
	}
	
	for(int i=1; i<=Lim; ++i) {
		int s=(i==1?1:(ll)i*phi[i]/2%P);
		for(int j=i; j<=Lim; j+=i)
			f[j]=(f[j]+s)%P;
	}
	for(int i=1; i<=Lim; ++i) f[i]=(ll)i*f[i]%P;
}
inline int ans() {
	cin>>n;
	return (ll)f[n]*kpow(n+1, n-1)%P;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	init();
	int T;
	cin>>T;
	while(T--)
		cout<<ans()<<"\n";
	return 0;
}

原文地址：http://www.cnblogs.com/JustinRochester/p/16830498.html