[ARC106F] Figures 题解

题目链接

点击打开链接

题目解法

这么神仙的推式子题

看到生成树计数，第一反应是 \(prufer\) 序列
考虑在 \(prufer\) 序列上搞这个东西
可以得到 \(ans=\sum\limits_{\sum\limits_{i=1}^n d_i=n-2}\binom{n-2}{d_1,d_2,...,d_n}\times \prod a_i^{\underline{d_i+1}}\)
考虑拆式子，\(ans=\sum\limits_{\sum\limits_{i=1}^n d_i=n-2}\frac{(n-2)!}{\prod\limits_{i=1}^nd_i!}\times \prod \frac{a_i!}{(a_i-d_i-1)!}\)
发现有一个类似组合数的形式，拆成组合数看一看（为什么要拆组合数？因为前面有 \(\sum\) 的所有情况的 \(\prod\)，拆成组合数可能可以用范德蒙德卷积）：\(ans=(n-2)!\prod\limits_{i=1}^n a_i\sum\limits_{\sum\limits_{i=1}^n d_i=n-2}\prod\limits_{i=1}^n\binom{a_i-1}{d_i}\)
可以发现后面的 \(\sum\limits_{\sum\limits_{i=1}^n d_i=n-2}\prod\limits_{i=1}^n\binom{a_i-1}{d_i}\) 是范德蒙德卷积，值为 \(\binom{\sum a_i-n}{n-2}\)
所以最后答案为 \((n-2)!\binom{\sum a_i-n}{n-2}\prod\limits_{i=1}^n a_i=\prod\limits_{i=1}^n a_i(\sum a_i-n)^{\underline{n-2}}\)

时间复杂度 \(O(n)\)
关键在于中间推式子那一部分想到拆成组合数计算

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int P=998244353;
int main(){
    int n=read(),s=0,ans=1;
    F(i,1,n){ int x=read();s=(s+x)%P,ans=1ll*ans*x%P;}
    F(i,0,n-3) ans=1ll*ans*(1ll*s-n-i+2*P)%P;
    printf("%d\n",ans);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}