CTS2019 珍珠
题意：
给定 (n,m,D)，计算有多少个长度为 (n) 的序列，每个元素的值为 ([1,D])，满足出现次数为奇数的颜色数小于 (n-2m) 的序列的数量。
(n,mle 10^9,Dle 10^5)
Solution
时隔一年，我来补这个题的原官方题解做法和 djq 神仙的解法了。
这个题目前大致有三种主流做法，今天打算集体补一下（容斥原本会的，打算重新推一下）
Algorithm1
- 容斥
设 (f_i) 表示单子数量恰好为 (i) 的序列的数量。
设 (g_i) 表示单子数量至少为 (i) 的序列的数量。
根据容斥理论，我们有：
于是有：
于是执行一次差值卷积即可。
考虑 (g_i)，不难注意到：
可以卷积了。复杂度 (mathcal O(nlog n))
Algorithm2
原标算（大力生成函数，神仙组合意义转换，找规律，归纳）
(mleftarrow n-2m)，这样我们的表述将更为简洁。
考虑通过生成函数将答案直接写出来，我们有：
接下来考虑 (inom{D}{k}inom{k}{i}inom{D-k}{j}) 的组合意义。
等价于从 (D) 个球选 (k) 个再选 (i) 个，再从剩下的 (D-k) 个选 (j) 个的方案数。
也等价于先选 (i+j) 个出来，再选 (i) 个出来，剩下的归为 (j)，再从 (D-(i+j)) 个中选 (k-i) 个出来。
于是有 (inom{D}{k}inom{k}{i}inom{D-k}{j}=inom{D}{i+j}inom{i+j}{i}inom{D-i-j}{k-i})
枚举 (i+j=t)，回代得到：
考虑后面的组合数的组合意义，等价于从 ((0,0)) 出发走到 ((j,i))，再走到 ((D-k,k)) 处的方案数。
这样可以考虑通过生成函数来解决路径计数的问题，具体的，我们先会行走 (t) 步，每一步的贡献都是 (1)，接下来我们走 (D-t) 步，每次走 (y) 贡献均为 (-1)
于是得到：
考虑设 (F(t,D)=sum_k^m (1+x)^t(1-x)^{D-t}[x^k])
我们发现 (F(0,d)=sum_k^m(1-x)^{d}[x^k]=sum_k^m inom{d}{k}(-1)^k)
通过手玩/人类智慧极限，我们发现 (F(0,0)=1,F(0,d)=(-1)^minom{d-1}{m})
具体论证可以通过帕斯卡定理来说明。
接下来我们进一步打表+手玩，发现 (F(x,y)=2F(x-1,y-1)-F(x-1,y))
知道结论后论证其正确性是 naive 的，但是正向推导是困难的，所以还是建议打表找规律。
不过事实上在计算 (F(1,6),F(2,6)...) 这些值的时候其实就可以看出来了。
那么设 (G_t(x)=sum_k F(t,k)x^k)，不难发现 (G_t(x)=G_{t-1}(x)(2x-1))
于是我们有：
其中，(G_0(x)) 是可以预处理的，设第 (i) 项系数为 (g_i)。
于是我们有：
一次 NTT 即可，复杂度 (mathcal O(nlog n))
我的实现不是很精细，大概是 (mathcal O(nlog P)) 的。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int P = 998244353 ;
const int Gi = 332748118 ;
const int G = 3 ;
const int N = 4e5 + 5 ;
int n, m, D, limit, Inv, L, R[N], f[N], A[N], B[N], f2[N], fac[N], inv[N] ;
int fpow(int x, int k) {
int ans = 1, base = x % P ;
while(k) {
if(k & 1) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
void init(int x) {
limit = 1, L = 0 ; while( limit < x ) limit <<= 1, ++ L ;
for(re int i = 0; i < limit; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)) ;
Inv = fpow( limit, P - 2 ) ;
}
void NTT(int *a, int type) {
for(re int i = 0; i < limit; ++ i) if( R[i] > i ) swap( a[i], a[R[i]] ) ;
for(re int k = 1; k < limit; k <<= 1 ) {
int d = fpow( (type == 1) ? G : Gi, (P - 1) / (k << 1) ) ;
for(re int i = 0; i < limit; i += (k << 1))
for(re int j = i, g = 1; j < i + k; ++ j, g = g * d % P) {
int nx = a[j], ny = a[j + k] * g % P ;
a[j] = (nx + ny) % P, a[j + k] = (nx - ny + P) % P ;
}
} if( !type ) rep( i, 0, limit ) a[i] = a[i] * Inv % P ;
}
int C(int x, int y) {
if( y > x ) return 0 ;
return fac[x] * inv[y] % P * inv[x - y] % P ;
}
signed main()
{
D = gi(), n = gi(), m = gi() ; fac[0] = inv[0] = 1 ;
m = n - 2 * m ;
if( m < 0 ) { puts("0") ; exit(0) ; }
rep( i, 1, D )
fac[i] = fac[i - 1] * i % P,
inv[i] = fpow( fac[i], P - 2 ) ;
f2[0] = f[0] = 1 ;
rep( i, 1, D ) f[i] = (m & 1) ? P - C(i - 1, m) : C(i - 1, m) ;
rep( i, 1, D ) f2[i] = f2[i - 1] * 2 % P ;
rep( i, 0, D ) A[i] = f[D - i] * f2[i] % P * inv[i] % P ;
rep( i, 0, D ) B[i] = (i & 1) ? P - inv[i] : inv[i] ;
init(D + D + 5), NTT(A, 1), NTT(B, 1) ;
rep( i, 0, limit ) A[i] = A[i] * B[i] % P ;
NTT(A, 0) ; int ans = 0 ;
rep( i, 0, D ) f[i] = A[i] * fac[i] % P ;
rep( i, 0, D ) ans = (ans + C(D, i) * fpow(2 * i - D + P, n) % P * f[i] % P) % P ;
ans = ans * fpow(f2[D], P - 2) % P ;
cout << ans << endl ;
return 0 ;
}
Algorithm3
djq 神仙的解法
同样 (mleftarrow n-2m)
考虑我们要求的其实是：
即
设 (Q_k(x)=inom{D}{k}(x-1)^k(x+1)^{D-k})，不难发现答案即 (frac{n!}{2^D}sum_{k=0}^D e^{-Dx}Q_k(e^{2x})[x^n])
假设我们知道了 (Q_k(x)) 的系数 (f^{(k)}_{i})，那么答案即为：
于是我们只需要维护 (Q(x)=sum_{k=0}^m Q_k(x))，这样答案即：
注意到：
根据万能并不的求导大法，我们有：
于是：
好吧，求导有点考验耐心，我突然不想学习这个解法了。