AGC019E

AGC019E

给定两个长度为 \(n\) 的 \(01\) 串 \(A_{1,2...n}\) 和 \(B_{1,2...n}\)，两者均恰好有 \(k\) 个 \(1\)，令 \(a_{1,2...k},b_{1,2...k}\) 分别表示其中所有 1 出现的下标构成的序列。

将 \(a\) 和 \(b\) 等概率随机排列，按 \(1\sim k\) 的顺序交换\(A_{a_i}\) 和 \(A_{b_i}\) 。令 \(P\) 表示操作完成后 \(A\) 与 \(B\) 相等的概率，求 \(P\times(k!)^2\)

答案对 \(998244353\) 取模。

\(n\le 10^4\)

Solution

设 \(n\) 为 A 和 B 中同时存在的 \(1\) 的数量。

设 \(m=k-n\)，同时设这些没有在对方出现过的 \(1\) 为特殊 \(1\)

那么不难发现这 \(A\) 中的特殊 \(1\) 有且仅有两种操作方式：

1. 直接在一次交换中变成 \(B\) 中的特殊 \(1\)
2. 其走到了某个 \(0\) 上，此时显然这个 \(0\) 由某个普通 \(1\) 得到，所以他必然也要先走到某个点处。最后会形成一种类似于单链的结果。

于是我们可以让特殊 \(1\) 先彼此配对，然后在考虑每个特殊 \(1\) 可以占据这 \(n\) 个元素中某些元素，对于剩余的被孤立 \(x\) 个元素，不难随便如何操作均合法，于是他们对答案的贡献为 \((x!)^2\)。

考虑最后的操作序列长度为 \(k\)，我们发现依次操作单链对答案的贡献和其余点只需要保证内部顺序确定就一定合法，换而言之我们只需要考虑将他们放入到一个长度为 \(k\) 的序列上的方案，显然可以通过混合组合数来刻画。

同时，对于长度为 \(c_1+c_2+...\) 的单链集合，我们有 \(\frac{n!}{c_1!...c_m!}\) 种分配方式将 \(n\) 个非特殊 \(1\) 分入其中，同时，在序列摆放上其又会产生贡献，这些计数的处理需要通过 EGF 来解决。

于是不难发现实际要求的即 \(k!\cdot m!\sum_i (\sum\frac{x^j\times j!}{(j+1)!\times j!})^m[x^i]\times n! \frac{((n-i)!)^2}{(n-i)!(n-i)!}\)

设 \(F(x)=\sum \frac{x^j}{(j+1)!}\)

即 \(n!\cdot k!\cdot m!\sum^n F(x)^m[x^i]\)

问题瓶颈在于求解 \(F(x)^m\)，多项式快速幂可以做到 \(\mathcal O(n\log n)\)

当然，这个题没必要这么麻烦：

注意到 \(F(x)=\frac{e^x-1}{x}\)，考虑 \(F(x)^m=\frac{(e^x-1)^m}{x^m}\)

我们希望求 \(\sum^n F(x)^m[x^n]\) 等价于 \(\sum^{n}(e^x-1)^m[x^{i+m}]\)

考虑求解 \((e^x-1)^m[x^n]\to \sum_i \binom{m}{i}(-1)^i (n-i)^n\)

对于 \(n\) 次幂递推即可，复杂度为 \(\mathcal O(n^2)\)

\(Code\)：(快速幂)

#include<bits/stdc++.h>
using namespace std ;
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define re register
#define int long long
//视题目调节 
const int P = 998244353 ; 
const int Gi = 332748118 ;
const int G = 3 ; 
// 基本参数 
const int N = 4e5 + 5 ; 
int len, K, n, m, A[N], B[N], fc[N], iv[N] ; 
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‘ ) % P, cc = getchar() ;
	return cn * flus ;
}
int fpow( int x, int k ) {
	int ans = 1, base = x ;
	while( k ) {
		if( k & 1 ) ans = ans * base % P ; 
		base = base * base % P, k >>= 1 ;
	} return ans % P ; 
}
namespace Poly {
	int limit, L, Inv, R[N], inv[N], gi[N << 1], igi[N << 1] ; 
	void Init( int x ) {
		limit = 1, L = 0 ; while( limit < x ) limit <<= 1, ++ L ;
		rep( i, 0, limit ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ; 
		Inv = fpow( limit, P - 2 ) ;
	}
	void _init( int x ) { 
	// 此函数用于预处理阶乘+原根
	// 所以需要注意丢进来的x应当为最大范围 
		for( re int i = 0; i <= x; ++ i ) inv[i] = fpow( i, P - 2 ) ;
		Init( x + x ) ; int num = 0 ;
		for( re int k = 1; k < limit; k <<= 1 ) {
			int d = fpow( G, ( P - 1 ) / ( k << 1 ) ) ;
			for( re int j = 0, g = 1; j < k; ++ j, g = g * d % P ) gi[++ num] = g ;
		} num = 0 ;
		for( re int k = 1; k < limit; k <<= 1 ) {
			int d = fpow( Gi, ( P - 1 ) / ( k << 1 ) ) ;
			for( re int j = 0, g = 1; j < k; ++ j, g = g * d % P ) igi[++ num] = g ;
		} 
	}
	void NTT( int *a, int type ) { //NTT多项式乘法 
		for( re int i = 0; i < limit; ++ i ) if( i < R[i] ) swap( a[i], a[R[i]] ) ;
		int num = 0 ;
		for( re int k = 1; k < limit; k <<= 1 ) {
			for( re int i = 0; i < limit; i += ( k << 1 ) )
			for( re int j = i, d = num + 1; j < i + k; ++ j, ++ d ) {
				int Nx = a[j], Ny = a[j + k] * ( ( type == 1 ) ? gi[d] : igi[d] ) % P ;
				a[j] = ( Nx + Ny ) % P, a[j + k] = ( Nx - Ny + P ) % P ; 
			} num += k ;
		} 
		if( type != 1 ) rep( i, 0, limit ) a[i] = a[i] * Inv % P ; 
	}
	// 求逆 
	int H[N], Gx[N] ;
	void PolyInv( int *a, int x ) {
		Gx[0] = fpow( a[0], P - 2 ) ; int lim = 1 ; 
		while( lim < x ) {
			lim <<= 1, Init( lim << 1 ) ; 
			for( re int i = 0; i < lim; ++ i ) H[i] = a[i] ;
			NTT( H, 1 ), NTT( Gx, 1 ) ;
			for( re int i = 0; i < limit; ++ i ) Gx[i] = ( 2ll - Gx[i] * H[i] % P + P ) % P * Gx[i] % P ;
			NTT( Gx, 0 ) ; for( re int i = lim; i < limit; ++ i ) Gx[i] = 0 ;
		}
		for( re int i = 0; i <= x; ++ i ) a[i] = Gx[i] ;
		rep( i, 0, limit ) Gx[i] = H[i] = 0 ;
	} 
	void Deriv( int *a, int x ) { //求导 
		rep( i, 1, x ) a[i - 1] = a[i] * i % P ;
	}
	void Integ( int *a, int x ) { //积分 
		drep( i, 1, x ) a[i] = a[i - 1] * inv[i] % P ;
		a[0] = 0 ;
	}
	int Gt[N], F[N] ;
	void Polyln( int *a, int x ) {
		rep( i, 0, x ) F[i] = Gt[i] = a[i] ;
		PolyInv( Gt, x ), Deriv( F, x ) ; 
		Init( x << 1 ), NTT( Gt, 1 ), NTT( F, 1 ) ;
		rep( i, 0, limit ) F[i] = F[i] * Gt[i] % P ;
		NTT( F, 0 ), Integ( F, x ) ;
		rep( i, 0, x ) a[i] = F[i] ;
		rep( i, 0, limit ) F[i] = Gt[i] = 0 ;
	}
	int _Gt[N], _F[N], _H[N] ; 
	void Polyexp( int *a, int x ) { //值得注意的是，exp只有在a_0 x^0 中，a_0 = 0的时候才能求得
	//因为泰勒展开第一项中，有 G[0] = e^{a[0]} ，在此情况，此值=1 
		_Gt[0] = 1 ; int lim = 1 ; 
		while( lim < x ) {
			lim <<= 1 ; rep( i, 0, lim - 1 ) _F[i] = a[i], _H[i] = _Gt[i] ;
			Polyln( _H, lim ), Init( lim << 1 ) ;
			NTT( _Gt, 1 ), NTT( _H, 1 ), NTT( _F, 1 ) ;
			rep( i, 0, limit ) _Gt[i] = ( 1ll - _H[i] + _F[i] + P ) % P * _Gt[i] % P ;
			NTT( _Gt, 0 ) ; rep( i, lim, limit ) _Gt[i] = 0 ;
		}
		rep( i, 0, lim ) a[i] = _Gt[i] ;
	}
	void PolyKSM( int *a, int x, int k ) {
		Polyln( a, x ) ;
		rep( i, 0, x ) a[i] = a[i] * k % P ;
		Polyexp( a, x ) ;
	}
}
char s1[N], s2[N] ;  
signed main()
{
	scanf("%s", s1 + 1 ), scanf("%s", s2 + 1 ) ;
	len = strlen(s1 + 1) ;
	rep( i, 1, len ) {
		K += (s1[i] == ‘1‘) ;
		n += ((s1[i] == ‘1‘) && (s2[i] == ‘1‘)) ;
	}
	m = K - n ; 
	Poly::_init(K + K + 5) ; //注意此函数的范围 
	iv[0] = fc[0] = 1 ; 
	rep( i, 1, K ) fc[i] = fc[i - 1] * i % P, iv[i] = fpow( fc[i], P - 2 ) ; 
	rep( i, 0, K ) A[i] = iv[i + 1] ;
	Poly::PolyKSM( A, K, m ) ;
	int ans = 0 ;
	rep( i, 0, n ) ans = (ans + A[i]) % P ; 
	ans = ans * fc[m] % P * fc[K] % P * fc[n] % P ; 
	cout << ans << endl ; 
	return 0 ;
}

AGC019E

原文：https://www.cnblogs.com/Soulist/p/13754695.html