题解：AT_abc425_e [ABC425E] Count Sequences 2

include13_fAKe · 2025-09-28 12:59:21 · 题解

哈哈，橙题没场切。

令 b_i 为 a_i 的前缀和。倒序操作，每一次可以选 C_{b_i}^{a_i} 个答案，最终答案即可 \prod_{i=1}^{n}C_{b_i}^{a_i}。

用杨辉三角处理组合数即可。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int mod;
int C[5005][5005];
void init(){
    C[0][0]=1;
    for(int i=1;i<=5000;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
        }
    }
}
int a[5005]; 
int b[5005];
signed main(){
    int T=read();
    mod=read();
    init();
    while(T--){
        int n=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
            b[i]=b[i-1]+a[i];
        }
        int include13=1;    //之后回去除 
        for(int i=1;i<=n;i++){
            include13*=C[b[i]][a[i]];
            include13%=mod;
//          cout<<'*'<<include13<<endl; 
        } 
        write2(include13);
    } 
    putchar('\n');
    return 0;
} //ABC425E