杂题
若干个正整数排成一个序列，其中数字 \(i\) 的出现次数为 \(r_i\)，对于每一个这样的序列，定义他的权值如下：
把这个序列首尾相接放在一个圆上，把这些数字分成若干相邻的段，使得每段都是在圆上相邻的数字，任意两段没有公共的元素，每一段中的数字都相同，相邻段中的数字不同，则这个序列的权值定义为所有段的长度之积。
求所有的序列的权值和对 \(998244353\) 取模。
注：虽然计算序列的权值的时候是圆排列，但互为循环排列的不同序列仍然被认为是不同的，如 \((1,2,1,2)\) 和 \((2,1,2,1)\) 被认为是不同的序列。
\(2\le n, \sum c_i \le 2\times 10^5\)
之前做 CF840C 的时候就想写来着，但是当时统计的是方案数，所以和答案一直对不上。遂弃之。
模拟赛考了，所以考虑写一份。任意模数可以采用 MTT，不是重点。
记 \(m = \sum c_i\)。
首先考虑序列问题如何计算。
承接先前的思路，我们考虑一个容斥。这里写出的式子和之前形式不是很相同，这是由于本题需要的式子分析能力更高，换个写法更容易看出来。
应用容斥后我们就需要计算不考虑限制的情况下的贡献如何计算，也就是将长度为 \(n\) 的序列任意分为 \(m\) 段，每一段长度乘积之和。
可以发现长度乘积本质上就是分割后从每一段中选择一个值的方案数，因此考虑插板法刻画。我们在序列中插入 \(m - 1\) 块板，并在这些板分割的 \(m\) 段中各选一个。这也就是从 \(n + m - 1\) 个元素中选择 \(2m - 1\) 个，然后按照 \(被选元素-板子-被选元素-\cdots-板子-被选元素\) 的方式分配，容易发现一种选择方案能且仅能导出一种分割+选择方案，因此有双射。
这部分的答案就是 \(f(n, m) = \dbinom{n + m - 1}{2m - 1}\)。
我们枚举序列 \(\langle a\rangle\)，意义是将颜色 \(i\) 任意分为 \(a_i\) 段。然后再枚举序列 \(\langle c\rangle\)，意义是颜色 \(i\) 被缩成的段数。
可以写出
发现 \(\dfrac{\left(\sum c_i\right)!}{\prod c_i!}\) 的部分是一个多重集组合数的形式，这个东西可以通过为每个元素分别构造 egf 后卷积起来构造。因此不妨构造生成函数，占位元是 \(k_{c_i}(x) = \dfrac{x^{c_i}}{c_i!}\) 来刻画性质。这样我们首先需要的是将 \(c\) 提前，也就是
\[\sum_{c} \left(\sum c_i\right)! \sum_{\forall c_i\le a_i \le r_i} \prod_{i = 1}^n (-1)^{a_i - c_i} f(r_i, a_i) \binom{a_i - 1}{c_i - 1}\frac{1}{c_i!} \]这个形式可以构造生成函数来枚举 \(k = c_i\)，第 \(i\) 种颜色对应的 egf 就是
\[F_i(x) = \sum_{k = 1}^{r_i} \sum_{k\le a_i \le r_i} (-1)^{a_i - k} f(r_i, a_i) \binom{a_i - 1}{k - 1}\frac{x^k}{k!} \]这个东西可以构造卷积后取后 \(r_i + 1\) 项得到。构造部分的总时间复杂度是 \(O(m\log m)\) 的。
iostream 说把上面的东西乘起来得到 \(F\) 后 \(m\sum_{i = 1}^{m} (i - 1)! [x^i]F(x)\) 就是答案，这确实。
具体为啥他不知道，我也不太知道。有懂的读者可以在评论区给讲讲。
然后考虑如何把序列问题的解法转到环上。
我们钦定颜色 \(1\) 其中一段段首为整个环的起始位置。然后删掉结尾也是一段 \(1\) 的情况。这等于是钦定了一段/两段是颜色 \(1\)。可以发现我们只需要把 egf \(F_1(x)\) 的系数向左平移 \(1, 2\) 就能得到答案了。这里注意不要把 \(k\) 次项里的 \(\dfrac{1}{k!}\) 也左移，这就需要我们首先用 ogf 的方式存储 \(F\)。
具体地，首先计算颜色 \(2\sim n\) 的 egf 的乘积 \(F'\)，然后用 \(F_1\) 左移 \(1\) 位得到的多项式乘 \(F'\)，再减去 \(F_1\) 左移 \(2\) 位得到的多项式乘 \(F'\) 的结果，得到最终多项式 \(F_{end}\)，设 \(ans = \sum_{k \ge 0} [x^k/k!] F_{end}\)。
\(F_{end}\) 的求得可以 \(O(m\log^2 m)\) 地做到。
\(ans\) 不是最终答案。
如果 \(1\) 颜色出现了 \(k\) 次，我们就会老老实实数 \(k\) 次，这是不行的，因此最开始的 \([x^k]F_1\) 得先除一个 \(k\)。
题目中要求每个循环移位作为不同情况出现，因此一个环的贡献要乘以循环节长度。然而按上面的做法没有考虑循环节，因此乘入 \(m\) 即可考虑循环节数量，并乘入了循环节长度作为贡献。
这样我们就在 \(O(m\log^2 m)\) 的复杂度内得到了答案。
code(iostream 的奇妙做法)
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
// int mod;
// const int mod = 10007;
// const int mod = 469762049, g = 3;
const int mod = 998244353; // const int g = 3;
// const int mod = 1004535809, g = 3;
// const int mod = 1e9 + 7;
// const int mod = 1e9 + 9;
// const int mod = 1e9 + 3579, bse = 131;
/* add / sub */ template<typename T1,typename T2>T1 add(T1 a,T2 b){return(a+=b)>=mod?a-mod:a;}template<typename T1,typename...Args>T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename T2>T1 sub(T1 a,T2 b){return(a-=b)<0?a+mod:a;}template<typename T1,typename...Args>T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename T2>void addi(T1&a,T2 b){(a+=b)>=mod?(a-=mod):true;}template<typename T1,typename...Args>void addi(T1&a,Args...b){addi(a,add(b...));}template<typename T1,typename T2>void subi(T1&a,T2 b){(a-=b)<0?(a+=mod):true;}template<typename T1,typename...Args>void subi(T1&a,Args...b){subi(a,add(b...));}
/* Fastmod / mul */ struct FastMod{int m;ll b;void init(int _m){m=_m;if(m==0)m=1;b=((lll)1<<64)/m;}FastMod(int _m){init(_m);}int operator()(ll a){ll q=((lll)a*b)>>64;a-=q*m;if(a>=m)a-=m;return a;}}Mod(mod);int mul(int a,int b){return Mod(1ll*a*b);}template<typename T1,typename T2>int mul(T1 a,T2 b){return Mod((long long)(1ll*a*b));}template<typename T,typename...Args>int mul(T a,Args...b){return mul(a,mul(b...));}template<typename T1,typename T2>void muli(T1&a,T2 b){a=Mod(1ll*a*b);}template<typename T1,typename...Args>void muli(T1&a,Args...b){muli(a,mul(b...));} // /* trivial multiple function(idk whether its useful*/ int mul(int a, int b) { return 1ll * a * b % mod; } template <typename T1, typename T2> int mul(T1 a, T2 b) { return (long long)(1ll * a * b) % mod; } template <typename T, typename ...Args> int mul(T a, Args ...b) { return mul(a, mul(b...)); }
/* qp fac C */ template<typename T1,typename T2>T1 qp(T1 a,T2 b){T1 ret=1;for(;b>0;a=1ll*a*a%mod,b>>=1)if(b&1)ret=mul(ret,a);return ret;}vi __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void ___prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=mul(i,__fac[i-1]),__inv[i]=mul((mod-mod/i),__inv[mod%i]),__ifc[i]=mul(__inv[i],__ifc[i-1]);}inline int fac(int x){return ___prep(x+1),__fac[x];}inline int ifc(int x){return ___prep(x+1),__ifc[x];}inline int inv(int x){return ___prep(x+1),__inv[x];}inline int C(int n,int m){if(n<m or n<0 or m<0)return 0;return mul(fac(n),ifc(m),ifc(n-m));}
/* sum of i^k */ int S(int n,int k){vector<int>__pre(k+4),__suf(k+4),__pw(k+4),__pri(k+4);vector<bool>__vis(k+4,0);__pw[1]=1;for(int i=2,cnt=0;i<=k+2;++i){if(!__vis[i])__pri[++cnt]=i,__pw[i]=qp(i,k);for(int j=1;j<=cnt and i*__pri[j]<=k+2;++j){__vis[i*__pri[j]]=1;__pw[i*__pri[j]]=mul(__pw[i],__pw[__pri[j]]);if(i%__pri[j]==0)break;}}rep(i,2,k+2)__pw[i]=add(__pw[i],__pw[i-1]);__pre[0]=__suf[k+3]=1;rep(i,1,k+2)__pre[i]=mul(__pre[i-1],(n-i+mod));pre(i,k+2,1)__suf[i]=mul(__suf[i+1],(n-i+mod));int tmp=0,ret=0;rep(i,1,k+2){if((k-i)&1)subi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));else addi(ret,mul(__pw[i],__pre[i-1],__suf[i+1],ifc(i-1),ifc(k+2-i)));}return ret;}
// /* inv 2/3/6 / phi */ constexpr int __var_pow(int a, int b) { int ret = 1; for (; b > 0; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; } constexpr int __var_phi(int x) { if (x <= 2) return 1; int ret = x; for (int i = 2; 1ll * i * i <= x; ++i) if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) ret = ret / x * (x - 1); return ret; } const int __phi_mod = __var_phi(mod); const int inv2 = __var_pow(2, __phi_mod - 1), inv3 = __var_pow(3, __phi_mod - 1), inv6 = __var_pow(6, __phi_mod - 1);
int qp(int a, int b = mod - 2, int p = mod) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % p;
a = 1ll * a * a % p;
b >>= 1;
} return ret;
}
using db = double;
struct cp {
db x, y;
cp(db real = 0, db imag = 0) : x(real), y(imag){};
cp operator+(cp b) const { return {x + b.x, y + b.y}; }
cp operator-(cp b) const { return {x - b.x, y - b.y}; }
cp operator*(cp b) const { return {x * b.x - y * b.y, x * b.y + y * b.x}; }
};
using vcp = vector<cp>;
namespace FFT {
const db pi = acos(-1);
vcp Omega(int L) {
vcp w(L); w[1] = 1;
for (register int i = 2; i < L; i <<= 1) {
auto w0 = w.begin() + i / 2, w1 = w.begin() + i;
cp wn(cos(pi / i), sin(pi / i));
for (register int j = 0; j < i; j += 2)
w1[j] = w0[j >> 1], w1[j + 1] = w1[j] * wn;
} return w;
} auto W = Omega(1 << 21);
void DIF(cp *a, int n) {
cp x, y;
for (register int k = n >> 1; k; k >>= 1)
for (register int i = 0; i < n; i += k << 1)
for (register int j = 0; j < k; ++j)
x = a[i + j], y = a[i + j + k],
a[i + j + k] = (x - y) * W[k + j], a[i + j] = x + y;
}
void IDIT(cp *a, int n) {
cp x, y;
for (register int k = 1; k < n; k <<= 1)
for (register int i = 0; i < n; i += k << 1)
for (register int j = 0; j < k; ++j)
x = a[i + j], y = a[i + j + k] * W[k + j],
a[i + j + k] = x - y, a[i + j] = x + y;
const db Inv = 1. / n;
rep(i, 0, n - 1) a[i].x *= Inv, a[i].y *= Inv;
reverse(a + 1, a + n);
}
}
namespace Polynomial {
using poly = vector<int>;
void DFT(vcp &a) { FFT::DIF(a.data(), a.size()); }
void IDFT(vcp &a) { FFT::IDIT(a.data(), a.size()); }
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
poly conv(const poly &a, const poly &b, const int&P = mod) {
int n = a.size(), m = b.size(), o = n + m - 1, l = norm(o);
vcp A(l), B(l), c0(l), c1(l);
for (register int i = 0; i < n; i++) A[i] = cp(a[i] & 0x7fff, a[i] >> 15);
for (register int i = 0; i < m; i++) B[i] = cp(b[i] & 0x7fff, b[i] >> 15);
FFT::DIF(A.data(), l), FFT::DIF(B.data(), l);
for (register int k = 1, i = 0, j; k < l; k <<= 1)
for ( ; i < k * 2; i++) {
j = i ^ k - 1;
c0[i] = cp(A[i].x + A[j].x, A[i].y - A[j].y) * B[i] * 0.5;
c1[i] = cp(A[i].y + A[j].y, -A[i].x + A[j].x) * B[i] * 0.5;
}
FFT::IDIT(c0.data(), l), FFT::IDIT(c1.data(), l);
poly res(o);
for (register int i = 0; i < o; i++) {
ll c00 = c0[i].x + 0.5, c01 = c0[i].y + 0.5, c10 = c1[i].x + 0.5, c11 = c1[i].y + 0.5;
res[i] = (c00 + ((c01 + c10) % P << 15) + (c11 % P << 30)) % P;
}
return res;
}
poly shiftcoeff(const poly& f, const int& w = 1) {
if (w + 1 > f.size()) return poly();
poly ret((int)f.size() - w);
if (ret.size() == 0) return ret;
for (int i = w; i < f.size(); ++ i)
ret[i - w] = f[i];
return ret;
}
poly toEGF(const poly& f, const int P = mod) {
poly ret(f);
for (int i = 0; i < ret.size(); ++ i)
ret[i] = 1ll * ret[i] * ifc(i) % P;
return ret;
}
} using namespace Polynomial;
int n, m, r[N];
poly F[N], t1, t2;
poly dac(int l, int r) {
if (l == r) return toEGF(F[l]);
int mid = l + r >> 1;
return conv(dac(l, mid), dac(mid + 1, r));
}
signed main() {
cin >> n; rep(i,1,n) cin >> r[i];
rep(i,1,n) {
m += r[i]; t1.clear(), t2.clear();
t1.resize(r[i] + 1), t2.resize(r[i] + 1);
rep(j,1,r[i]) t1[j] = mul(C(r[i] + j - 1, r[i] - j), fac(j - 1));
rep(j,0,r[i]) t2[r[i] - j] = mul((j & 1) ? mod - 1 : 1, ifc(j));
F[i] = shiftcoeff(conv(t1, t2), r[i]);
rep(j,1,r[i]) F[i][j] = mul(F[i][j], ifc(j - 1));
F[i][0] = 0;
}
poly f = dac(1, n);
int ans = 0;
for (int i = 1; i <= m; ++ i)
addi(ans, mul(f[i], fac(i - 1)));
cout << mul(ans, m) << '\n';
}