AUOJ422 生成无向图

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

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

然后是推式子:

然后运用一个组合恒等式

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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();
}
文章作者: yijan
文章链接: https://yijan.co/2021/04/19/auoj422-sheng-cheng-wu-xiang-tu/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog