壹、题目描述 ¶
贰、题解 ¶
\(a,b\) 都数组由 \([1,n]\) 中的数字组成， \(a\) 数组长度为 \(n\) ，并且满足给任意元素加上任意非负数后能变成某个排列， \(b\) 数组长度为 \(k\) ，满足 \(a_{b_1}=a_{b_2}=...=a_{b_k}\) （注意我们没有要求 \(a,b\) 数组的元素两两不同）
问有多少个本质不同的数组对 \((a,b)\) ，答案取模 \(998244353\).
保证 \(1\leq n\leq10^9,1\leq k\leq 10^5\).
解法
发现 \(a,b\) 两个数组的计数还算比较独立吧，我们先考虑 \(a\) 数组怎么计数。
设 \(c_i\) 为数字 \(i\) 的出现次数，则限制可以翻译为 \(\sum_{j=i}^{n} c_j\leq n-i+1\) ，但是这样根本算不出来，因为这个限制牵扯到的东西太多了，我们想要更加独立的限制。
不妨把题目换个说法：我们有 \(n+1\) 个位置排成一排，有 \(n\) 个人要坐进来，第 \(i\) 个人一开始会到位置 \(a_i(1\leq a_i\leq n)\)，如果位置已满就往编号大的位置走，如果最后剩下的位置是 \(n+1\) 的话就是一个合法的 \(a\) 序列。
这是一个经典的序列转等概率环模型（第二次见了），所以我们可以改写题目为：有 \(n+1\) 个位置排成一个环，有 n 个人要坐进来，第 \(i\) 个人一开始会到位置 \(a_i(1\leq a_i\leq n+1)\)，如果位置已满就往右边走，如果最后剩下的位置是 \(n+1\) 的话就是一个合法的 \(a\) 序列。
因为是一个环并且初始到每个点的概率相同，所以每个点被空出来的概率也是相同的，不难发现方案数就是 \((n+1)^{n-1}\).
我们再深入下去剖析这个模型，对于每种合法的 \(a\) 序列都可以映射到 \(n\) 种不同的不合法序列，因为如果我们让 \(a_i\) 变成 \([(a_i+x-1)\bmod(n+1)]+1\) ，那么空出的位置 \(t\) 会变成 \([](x+t-1)\bmod(n+1)]+1\) ，由此引出一个重要的性质：对于这 \(n+1\) 个方案来说，数字的分布情况是不会改变的，所以我们可以统计出所有排列的答案再除以 \(n+1\).
对于 \(b\) 的计算，实际上我们枚举 \(a\) 里面有多少个相同的数字，让 \(b\) 来对应选择就行了。
实际上我们要算的就是
\[\sum_{i=0}^n{n\choose i}\times n^{n-i}i^k \]由于 \(b\) 并不要求不同，所以我们可以随便选择。考虑这个式子的化简：
\[\newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \] \[\begin{aligned} &\sum_{i=0}^n{n\choose i}\times n^{n-i}i^k \\ =&\sum_{i=0}^n{n\choose i}\times n^{n-i}\sum_{j=0}^i{i\choose j}\string{k}{j}j! \\ =&\sum_{i=0}^n\sum_{j=0}^i{n\choose i}{i\choose j}\string{k}{j}j!n^{n-i} \\ =&\sum_{i=0}^n\sum_{j=0}^i{n\choose j}{n-j\choose i-j}\string{k}{j}j!n^{n-i} \\ =&\sum_{j=0}^n{n\choose j}\string{k}{j}j!\sum_{i=j}^n{n-j\choose i-j}n^{n-i} \\ =&\sum_{j=0}^n{n\choose j}\string{k}{j}j!\sum_{i=0}^{n-j}{n-j-i\choose i}n^{n-j-i} \\ =&\sum_{j=0}^n{n\choose j}\string{k}{j}j!(n+1)^{n-j} \end{aligned} \]而由于
\[\string{k}{j}=0\quad (j>k) \]所以我们可以调整一下 \(j\) 的取值：
\[\sum_{j=0}^k{n\choose j}\string{k}{j}j!(n+1)^{n-j} \]这样组合数就不需要算到 \(n\le 10^9\) 了，但是还是只能使用递推。
若
\[f(i)\overset\Delta={n\choose i}\string{k}{i}i! \\ g(i)\overset\Delta=(n+1)^i \]那么，最后的答案就是
\[(f\cdot g)(n) \]使用 \(\tt fft\) 或者 \(\tt ntt\) 进行计算。
至于如何求 \(\string{k}{i}\)，因为我们有
\[\string{k}{i}={1\over i!}\sum_{j=0}^i(-1)^j{i\choose j}(i-j)^k=\sum_{j=0}^i{(-1)^j\over j!}\cdot {(i-j)^k\over (i-j)!} \]若
\[h(i)\overset\Delta={(-1)^i\over i!} \\ u(i)\overset\Delta={i^k\over i!} \]那么
\[S=h\cdot u \]就可以得到斯特林数组了.
叁、参考代码 ¶
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
// #define NDEBUG
#include<cassert>
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
const int mod=998244353;
const int primitive_root=3;
const int inverse_primitive_root=332748118;
const int maxk=1e5;
inline int qkpow(int a, int n){
int ret=1;
for(; n>0; n>>=1, a=1ll*a*a%mod)
if(n&1) ret=1ll*ret*a%mod;
return ret;
}
namespace poly{
int G[2][55], n, invn;
vector<int>rev;
inline void initial(){
rep(j, 1, 50){
G[0][j]=qkpow(primitive_root, (mod-1)/(1<<j));
G[1][j]=qkpow(inverse_primitive_root, (mod-1)/(1<<j));
}
}
inline void prepare(int N){
for(n=1; n<N; n<<=1);
invn=qkpow(n, mod-2);
rev.resize(n);
rep(i, 0, n-1) rev[i]=(rev[i>>1]>>1)|((i&1)? (n>>1): 0);
}
inline void ntt(vector<int>&f, int opt){
f.resize(n);
rep(i, 0, n-1) if(i<rev[i])
swap(f[i], f[rev[i]]);
for(int p=2, cnt=1; p<=n; p<<=1, ++cnt){
int len=p>>1, w=G[opt][cnt];
for(int k=0; k<n; k+=p){
int buf=1, tmp;
for(int i=k; i<k+len; ++i, buf=1ll*buf*w%mod){
tmp=1ll*f[i+len]*buf%mod;
f[i+len]=(f[i]+mod-tmp)%mod;
f[i]=(f[i]+tmp)%mod;
}
}
}
if(opt==1){
rep(i, 0, n-1)
f[i]=1ll*f[i]*invn%mod;
}
}
}
int fac[maxk+5], finv[maxk+5], C[maxk+5];
inline void precalc(){
fac[0]=1;
rep(i, 1, maxk) fac[i]=1ll*fac[i-1]*i%mod;
finv[maxk]=qkpow(fac[maxk], mod-2);
drep(i, maxk-1, 1) finv[i]=1ll*finv[i+1]*(i+1)%mod;
finv[0]=1;
}
int n, k;
vector<int>f, u;
signed main(){
poly::initial(); // pay attention!
precalc();
n=readin(1), k=readin(1);
C[0]=1;
rep(i, 1, k) C[i]=1ll*C[i-1]*(n-i+1)%mod*qkpow(i, mod-2)%mod;
f.resize(k+1); u.resize(k+1);
rep(i, 0, k){
f[i]=(i&1)? (mod-finv[i]): finv[i];
u[i]=1ll*qkpow(i, k)*finv[i]%mod;
}
poly::prepare(k*2+5);
poly::ntt(f, 0); poly::ntt(u, 0);
rep(i, 0, poly::n-1) f[i]=1ll*f[i]*u[i]%mod;
poly::ntt(f, 1);
int ans=0;
rep(i, 0, k) {
ans=(ans+1ll*C[i]*f[i]%mod*fac[i]%mod*qkpow(n+1, n-i)%mod)%mod;
}
writc(ans);
return 0;
}
肆、关键的地方 ¶
对于 \(n^k\)，有时候它和组合数不是很配，我们可以使用等式：
\[n^k=\sum_{i=0}^k{n\choose i}\string{k}{i}i! \]使用组合意义进行说明：将 \(k\) 个数划分到 \(n\) 个集合（地位不等），允许为空，那么我们枚举非空集个数，根据第二类斯特林数，将 \(k\) 个数分为 \(i\) 个非空集（地位等价），再乘上集合的排列，以及从 \(n\) 个集合中选择 \(i\) 个，求和，就可以得到。
另外，有
\[{n\choose i}{i\choose j}={n\choose j}{n-j\choose i-j} \]可以根据组合意义进行分析。
对于第二类斯特林数，这个卷积方法很妙，我们都知道：
\[\string{n}{m}=\string{n-1}{m-1}+m\string{n-1}{m} \]但是我们也可以通过容斥空集的数量进行求解：
\[\string{n}{m}={1\over m!}\sum_{i=0}^m(-1)^i{m\choose i}(m-i)^n=\sum_{i=0}^m{(-1)^i\over i!}\cdot{(m-i)^n\over (m-i)!} \\ \]求同一行的第二类斯特林数，即 \(n\) 固定的情况，就可以用这个卷。