T1
题意：
有 \(N\) 个节点，第 \(i\) 个节点上有 \(d[i]\) 个本质不同的孔，现在用 \(N-1\) 条边将 \(N\) 个节点连成一棵树（一个孔只能使用一次），定义两棵树相同当且仅当对于每一条边，它插入的两个孔在两棵树中相同。问可以连出多少不同的树，对 \(M\) 取模。
解题思路
考虑对于每一个非根节点，定义它连接父节点的孔为特殊孔。对于根节点，选取一个与儿子相连的孔为特殊孔。
红色为特殊孔
对于每一个特殊孔，它的选取是独立的，所以选取特殊孔的方案数是 \(\prod_{i=1}^{n} d[i]\)
考虑只要每一条边连接的两个孔相同，这条边就是唯一确定的。所以只需对于每一个节点算出它选父节点的孔的方案数，乘法原理求解即可。
先考虑孔可以重复的情况。令\(S=\sum_{i=1}^{N} d[i]\)在 \(Prufer\) 序列中，每一个节点有 \(S-N\) 种方案选取父节点（ \(N\) 个已选的特殊孔），则共有\(\left ( S-N \right ) ^{\left ( N-2 \right ) }\)种方案。但孔不能重复使用，所以对于第 \(i\) 个节点，方案数需减去前 \(i-1\) 个节点选过的父节点，即方案数为\((S-N-i+1)\),即选取父节点的方案数为\(\prod_{i=1}^{n}\left ( S-N-i+1 \right )\)
根据乘法原理，答案为\(\prod_{i=1}^{n} d[i] \times \prod_{i=1}^{n}\left ( S-N-i+1 \right )\%M\)
CODE:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,mod;//N，模数M
int sum=0;//S
int kv=1;//累乘计数器
int d[1000001];
signed main(){
cin>>n>>mod;
for(int i=1;i<=n;i++){
cin>>d[i];
sum+=d[i];
}
for(int i=1;i<=n;i++){
kv*=(d[i]%mod);
kv%=mod;
}
for(int i=1;i<=n-2;i++){
kv*=((sum-n-i+1)%mod);
kv%=mod;
}
cout<<kv;
return 0;
}
T2
题意：
给定一个正整数序列，将它划分成了最少个连续子段，使得每段的元素都严格递增。给定原序列中数字的值域，每个数字的出现次数和分出的子段数，求有多少种可能的原序列。
第一行两个整数N,K分别表示原序列值域与最少划分段数。
第二行N个整数，第i个整数 $a_{i} $ 表示原序列中i的出现次数。
解题思路
先设 $f\left ( k \right ) $ 为至少有k个，但不一定恰好有k个严格递增子段的方案数。
先不考虑空的集合不合法，将数随机填进这k割几何中，方案总数是\(\prod C_{a[i]}^{k}\)
再考虑减去重复的方案数,对于任意的一组i<j,f(j)的构造方案都有可能有j-i个空子段。
考虑插板法，令\(tot=\sum a[i]\)系数为\(C_{i-j}^{tot+i-j}\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int c[5001][5001];
int n,k;
int a[100];
int dp[5001];
int tot;
void pre(){
for(int i=0;i<=5000;i++){
c[i][i]=c[i][0]=1;
}
for(int i=1;i<=5000;i++){
for(int j=1;j<=5000;j++){
c[i][j]=c[i-1][j]%mod+c[i-1][j-1]%mod;
c[i][j]%=mod;
}
}
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
pre();
for(int i=1;i<=n;i++){
tot+=a[i];
}
for(int i=1;i<=k;i++){
dp[i]=1;
for(int j=1;j<=n;j++){
dp[i]=dp[i]%mod*c[i][a[j]]%mod;
dp[i]%=mod;
}
for(int j=1;j<i;j++){
dp[i]-=(dp[j]%mod*c[tot+i-j][i-j]%mod);
dp[i]+=mod;
dp[i]%=mod;
}
}
cout<<(dp[k]+mod)%mod;
return 0;
}