This is not the end.

0%

luogu P6151 [集训队作业2019] 青春猪头少年不会梦到兔女郎学姐

Posted on

Sol

定义一个序列是好的，当且仅当它以 $1$ 开始且不以 $1$ 结尾。

任意一个序列 $S$，假设它对应的圆排列中有 $c(S)$ 段 $1$，那么它的循环移位中有 $c(S)$ 个好的序列（这其中可能有相同的好序列）。也就是说，所有的好序列的、等于 $S$ 的循环移位的数量为 $c(S)$。

设 $val(S)$ 为序列 $S$ 的权值（与题目中的定义相同），那么

因为序列的长度是固定的，我们只需要统计 $\sum_{\text{P是符合题意的好序列}} \frac{val(P)}{c(P)}$ 就能得到答案。

将 $a$ 个相同的数字划分成 $b$ 段的所有方案的权值和为

考虑到 $\prod_i x_i$ 的组合意义相当于是从每段里面再选出一个球，把选的这个球当成板子，可以得到上式等价于

先枚举每种数字在最终的序列中形成了多少段，然后由于要求同种数字的段不能相邻，所以再枚举同种数字的哪些段被粘在了一起（容斥）。不为 $1$ 的数字，它的 EGF 为（假设这种数字共有 $a$ 个）

可以一次 FFT 算出来。

而对于数字 $1$，容斥的时候除了可以把相邻的段粘在一起，还可以把最后一段和结尾粘在一起，并且第一段在序列中的位置是确定了的，不参与排列，所以它的 EGF 为（仍然设 $a=c_1$）

也可以一次 FFT 算出来。

最后我们需要算的是每个数字的 EGF 的乘积，分治 FFT 即可。

Code

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int mod=998244353;
const int N=2e5+10;
ll Pow(ll x,int y) { ll res=1; for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod; return res; }

namespace Poly {
	const int N=(1<<18)+10;
    int wn[2][N],rev[N];
    void getwn(int l) {
        for(int i=1;i<(1<<l);i<<=1) {
            int w0=Pow(3,(mod-1)/(i<<1)),w1=Pow(3,mod-1-(mod-1)/(i<<1));
            wn[0][i]=wn[1][i]=1;
            for(int j=1;j<i;++j)
                wn[0][i+j]=wn[0][i+j-1]*(ll)w0%mod,
                wn[1][i+j]=wn[1][i+j-1]*(ll)w1%mod;
        }
    }
    void getr(int len) { for(int i=1;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)*(len>>1)); }
    void FFT(int *A,int len,int f) {
        for(int i=0;i<len;++i) if(rev[i]<i) swap(A[i],A[rev[i]]);
        for(int l=1;l<len;l<<=1)
            for(int i=0;i<len;i+=l<<1)
                for(int j=0;j<l;++j) {
                    int t0=A[i+j],t1=A[i+l+j]*(ll)wn[f][l+j]%mod;
                    A[i+j]=(t0+t1)%mod,A[i+l+j]=(t0-t1)%mod;
                }
        if(f==1) {
            int Inv=Pow(len,mod-2);
            for(int i=0;i<len;++i) A[i]=A[i]*(ll)Inv%mod;
        }
    }  
	void Mul(int *A,int *B,int *C,int n,int m,int l3) {
        static int a[N],b[N];
        int len=1; while(len<n+m-1||len<l3) len<<=1; getr(len);
        for(int i=0;i<len;++i) a[i]=b[i]=0;
        for(int i=0;i<n;++i) a[i]=A[i];
        for(int i=0;i<m;++i) b[i]=B[i];
        FFT(a,len,0),FFT(b,len,0); for(int i=0;i<len;++i) a[i]=a[i]*(ll)b[i]%mod; FFT(a,len,1);
        for(int i=0;i<l3;++i) C[i]=a[i];
    }
    void Mul(int *A,int *B,int *C,int n,int m) { Mul(A,B,C,n,m,n+m-1); }
    inline void Mul(vector<int> &A,vector<int> &B,vector<int> &C) {
    	static int a[N],b[N];
        int len=1; while(len<A.size()+B.size()-1) len<<=1; getr(len);
        for(int i=0;i<len;++i) a[i]=b[i]=0;
        for(int i=0;i<A.size();++i) a[i]=A[i];
        for(int i=0;i<B.size();++i) b[i]=B[i];
        FFT(a,len,0),FFT(b,len,0); for(int i=0;i<len;++i) a[i]=a[i]*(ll)b[i]%mod; FFT(a,len,1);
        C.resize(A.size()+B.size()-1);
        for(int i=0;i<C.size();++i) C[i]=a[i];
    }
}

vector<int> g[N],s[N<<2];
inline void solve(int l,int r,int c) {
	if(l==r) return (void)(s[c]=g[l]);
	int mid=l+r>>1;
	solve(l,mid,c<<1),solve(mid+1,r,c<<1|1);
	Poly::Mul(s[c<<1],s[c<<1|1],s[c]);
	s[c<<1].clear();
	s[c<<1|1].clear();
}
ll fac[N<<1],inv[N<<1];
// ll A[N],B[N],C[N];
int A[N],B[N],C[N];
ll f[N];
//ll sum[N],tmp[N];
//int len;
inline void getfac(int n) {
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2); for(int i=n;i>=1;--i) inv[i-1]=inv[i]*i%mod;
}
inline ll binom(int n,int m) { return fac[n]*inv[m]%mod*inv[n-m]%mod; }
int ra[N];
int main() {
	int m; rd(m);
	getfac(400000);
	Poly::getwn(18);
//	sum[0]=1;
	int coe=0;
	for(int now=1,a;now<=m;++now) {
		rd(a),coe+=a;
		for(int i=0;i<=a;++i) A[i]=B[i]=0;
		if(now==1) {
			for(int i=1;i<=a;++i) A[i]=binom(a+i-1,2*i-1)*fac[i-1]%mod*(i&1?1:-1);
			for(int i=1;i<=a;++i) B[a-i]=inv[i-1];
			Poly::Mul(A,B,C,a+1,a+1);
			for(int i=0;i<a;++i) f[i]=C[i+a]*inv[i]%mod*inv[i+1]%mod*(i&1?-1:1);
			
//			for(int i=1;i<=a;++i) B[i]=inv[i-1];
//			for(int i=1;i<=a;++i) for(int j=1;j<=i;++j) (C[i-j]+=A[i]*B[j]%mod)%=mod;
//			for(int i=0;i<a;++i) f[i]=C[i]*inv[i]%mod*inv[i+1]%mod*(i&1?-1:1),C[i]=0;
		}
		else {
			for(int i=1;i<=a;++i) A[i]=binom(a+i-1,2*i-1)*fac[i-1]%mod*(i&1?-1:1);
			for(int i=0;i<a;++i) B[a-i]=inv[i];
			Poly::Mul(A,B,C,a+1,a+1);
			for(int i=1;i<=a;++i) f[i]=C[i+a]*inv[i]%mod*inv[i-1]%mod*(i&1?-1:1);
//			for(int i=0;i<a;++i) B[i]=inv[i];
//			for(int i=1;i<=a;++i) for(int j=0;j<i;++j) (C[i-j]+=A[i]*B[j]%mod)%=mod;
//			for(int i=1;i<=a;++i) f[i]=C[i]*inv[i]%mod*inv[i-1]%mod*(i&1?-1:1),C[i]=0;
		}
		for(int i=0;i<=a;++i) g[now].PB(f[i]),f[i]=0;
//		for(int i=0;i<=a;++i)
//		for(int j=0;j<=len;++j)
//			(tmp[i+j]+=f[i]*sum[j]%mod)%=mod;
//		len+=a;
//		for(int i=0;i<=len;++i) sum[i]=tmp[i],tmp[i]=0;
//		for(int i=0;i<=a;++i) f[i]=0;
	}
	solve(1,m,1);
	int ans=0;
//	for(int i=0;i<=len;++i) (ans+=sum[i]*fac[i]%mod)%=mod;
	for(int i=0;i<s[1].size();++i) (ans+=s[1][i]*fac[i]%mod)%=mod;
	ans=1ll*ans*coe%mod;
	printf("%d",(ans+mod)%mod);
	return 0;
}