AUOJ422 生成无向图

考虑对于一个数组 a1,,na_{1,\dots ,n} 怎么求出答案,其中 00 为根。考虑每一条边 ifii \to f_i 的贡献,显然是 sizi(n+1sizi)siz_i(n+1-siz_i) 。那么我们可以枚举这个点的子树的 sizsiz 然后算这种情况的概率,而算概率则直接统计有多少种加边后的方案使得取到这个 sizsiz 然后除以总方案数 n!n! 即可。考虑方案数量的计算,如果确定后面有 ss 个点在子树内(不包括 ii ),这些点的父亲的方案分别是 1,2,3,,s1,2,3,\dots ,s ,因为第一个子树内的点的父亲必须是 ii ,第二个可以是第一个或者 ii …… 然后考虑这个子树之外(不包括 ii )的点。这些点的方案数显然依次是 1,2,,ns11,2,\dots,n-s-1 。最后考虑 ii 的父亲的方案数,它可以连向 0i10 \sim i-1 ,是 ii ,于是式子就是:

1n!i=1nAis=0ni(nis)s!(ns1)!i[(s+1)(n+1)(s+1)2]\frac{1}{n!}\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n-i} s s!(n-s-1)!i[(s+1)(n+1)-(s+1)^2]

为了方便,暂时不写最前面的 1n!\frac 1{n!} 了。

然后是推式子:

i=1nAis=0ni(nis)(ns1)!s!i[(s+1)(n+1)(s+1)2]=i=1nAii(ni)!s=0ni(ns1)!s!(nis)!s![(s+1)(n+1)(s+1)2]=i=1nAii(ni)!(i1)!s=0ni(ns1)!(nis)!(i1)![(s+1)(n+1)(s+1)2]=i=1nAi(ni)!i!s=0ni(ns1i1)[(s+1)(n+1)(s+1)2]\begin{aligned} &\sum_{i=1}^n A_i \sum_{s=0}^{n-i} \binom {n - i}s(n-s-1)!s!i[(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i i(n-i)!\sum_{s=0}^{n-i} \frac {(n-s-1)!}{s!(n-i-s)!}s![(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i i(n-i)!(i-1)!\sum_{s=0}^{n-i} \frac {(n-s-1)!}{(n-i-s)!(i-1)!}[(s+1)(n+1)-(s+1)^2]\\ =&\sum_{i=1}^n A_i (n-i)!i!\sum_{s=0}^{n-i} \binom{n-s-1}{i-1} [(s+1)(n+1)-(s+1)^2]\\ \end{aligned}

然后运用一个组合恒等式

i=0n(ia)(nib)=(n+1a+b+1)\sum_{i=0}^n \binom{i}{a}\binom{n-i}{b} = \binom{n+1}{a+b+1}

组合意义就是枚举分界点。

于是可以把 s+1s+1 变成 (s+11)\binom {s+1} 1 来解决掉,但是发现 (s+1)2(s+1)^2 无法运用组合恒等式了。于是我们考虑代入 (s+12)\binom{s+1}{2} ,最后再通过 x2=2(x2)+xx^2 = 2\binom x2 + x 推回即可。

=i=1nAi(ni)!i!s=0ni(ns1i1)[(s+1)n2(s+12)]=i=1nAi(ni)!i![(n+1i+1)n2(n+1i+2)]=i=1nAi(ni)!i![(n+1)!(i+1)!(ni)!n2(n+1)!(i+2)!(ni1)!]=(n+1)!i=1nAi[n(i+1)2(ni)(i+2)(i+1)]=(n+1)!i=1nAi(n+2)i(i+2)(i+1)\begin{aligned} =&\sum_{i=1}^n A_i (n-i)!i!\sum_{s=0}^{n-i} \binom{n-s-1}{i-1} \left[(s+1)n-2\binom{s+1}{2}\right]\\ =&\sum_{i=1}^n A_i (n-i)!i!\left[\binom{n+1}{i+1}n - 2\binom{n+1}{i+2}\right]\\ =&\sum_{i=1}^n A_i (n-i)!i!\left[\frac{(n+1)!}{(i+1)!(n-i)!}n - 2\frac{(n+1)!}{(i+2)!(n-i-1)!}\right]\\ =&(n+1)!\sum_{i=1}^n A_i \left[\frac{n}{(i+1)} - \frac{2(n-i)}{(i+2)(i+1)}\right]\\ =&(n+1)!\sum_{i=1}^n A_i \frac{(n+2)i}{(i+2)(i+1)}\\ \end{aligned}

最开始我们省略了一个 1n!\frac 1 {n!} 我们给它代回来

=(n+1)(n+2)i=1nAii(i+2)(i+1)=(n+1)(n+2)\sum_{i=1}^n A_i \frac{i}{(i+2)(i+1)}

然后就获得了一个看起来非常优秀的 O(n)O(n) 式子,甚至没必要算阶乘!

但是区间查询怎么做?我们可以把它写成一个差卷积的形式

ij=lAij+1(j+2)(j+3)\sum_{i-j=l} A_i \frac{j+1}{(j+2)(j+3)}

于是发现求的就是区间之内所有的位置提出来然后做差卷积之后在 ll 这个位置的和。于是我们可以分块,对每个块维护出 l=1nl=1\sim n 的上述式子的值,这个可以通过 NTT 在 O(n2Blogn)O(\frac{n^2}{B}\log n) 解决。

而查询直接 O(nB+B)O(\frac{n}{B}+B) 枚举中间的块以及两边散的,分别算贡献即可。

复杂度 O(nnlogn)O(n\sqrt{n\log n})

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
int n , q;
int A[MAXN] , bl[MAXN];
const int blo = 1200;

int iv[MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

int Wn[2][1000006];
void getwn( int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 ) {
		int w0 = Pow( 3 , ( P - 1 ) / ( mid << 1 ) ) , w1 = Pow( 3 , P - 1 - ( P - 1 ) / ( mid << 1 ) );
		Wn[0][mid] = Wn[1][mid] = 1;
		for( int i = 1 ; i < mid ; ++ i )
			Wn[0][mid + i] = Wn[0][mid + i - 1] * 1ll * w0 % P,
			Wn[1][mid + i] = Wn[1][mid + i - 1] * 1ll * w1 % P;
	}
}
int rev[MAXN];
void getr( int len ) {
	int l = __builtin_ctz( len ) - 1;
	for( int i = 1 ; i < len ; ++ i ) rev[i] = ( rev[i >> 1] >> 1 ) | ( ( i & 1 ) << l );
}
void NTT( int A[] , int len , int typ ) {
	for( int i = 0 ; i < len ; ++ i ) if( i < rev[i] ) swap( A[i] , A[rev[i]] );
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int j = i ; j < i + mid ; ++ j ) {
				int t0 = A[j] , t1 = A[j + mid] * 1ll * Wn[typ][j - i + mid] % P;
				A[j] = ( t0 + t1 > P ? t0 + t1 - P : t0 + t1 ) , A[j + mid] = ( t0 < t1 ? t0 - t1 + P : t0 - t1 );
			}
	if( typ ) for( int i = 0 , iv = Pow( len , P - 2 ) ; i < len ; ++ i ) A[i] = A[i] * 1ll * iv % P;
}

int S[406][200006];
int B[200006];

int f( int a ) {
	return ( a + 1 ) * 1ll * iv[a + 2] % P * iv[a + 3] % P;
}

void solve() {
	getwn( 1 << 18 );
	cin >> n >> q;
	rep( i , 1 , n + 114 ) iv[i] = Pow( i , P - 2 );
	rep( i , 1 , n ) scanf("%d",A + i);
	rep( i , 1 , n ) bl[i] = ( i - 1 ) / blo + 1;
	rep( i , 1 , n ) B[i] = f( n - i );
	int len = 1;
	while( len <= n + n ) len <<= 1;
	getr( len );
	NTT( B , len , 0 );
	rep( k , 1 , bl[n] ) {
		rep( i , ( k - 1 ) * blo + 1 , k * blo ) S[k][i] = A[i];
		NTT( S[k] , len , 0 );
		rep( i , 0 , len - 1 ) S[k][i] = S[k][i] * 1ll * B[i] % P;
		NTT( S[k] , len , 1 );
		rep( i , 1 , n ) S[k][i] = S[k][i + n];
		S[k][0] = 0;
		rep( i , n + 1 , len - 1 ) S[k][i] = 0;
	}
	rep( i , 1 , q ) {
		int l , r;
		scanf("%d%d",&l,&r);
		int as = 0;
		if( bl[l] == bl[r] ) {
			rep( j , l , r ) 
				as = ( as + f( j - l ) * 1ll * A[j] ) % P;
		} else {
			rep( j , l , bl[l] * blo ) as = ( as + f( j - l ) * 1ll * A[j] ) % P;
			rep( j , bl[r] * blo - blo + 1 , r ) as = ( as + f( j - l ) * 1ll * A[j] ) % P;
			rep( j , bl[l] + 1 , bl[r] - 1 ) as = ( as + S[j][l] ) % P;
		}
		printf("%d\n",as * 1ll * ( r - l + 2 ) % P * ( r - l + 3 ) % P);
	}
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}
\