题解：AT_abc425_e [ABC425E] Count Sequences 2

哈哈，橙题没场切。

令

b_i

为

a_i

的前缀和。倒序操作，每一次可以选

C_{b_i}^{a_i}

个答案，最终答案即可

\prod_{i=1}^{n}C_{b_i}^{a_i}

。

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

CPP

#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

题解：AT_abc425_e [ABC425E] Count Sequences 2

文章操作

相关推荐

评论

题解：AT_abc425_e [ABC425E] Count Sequences 2