比赛 Asm_Def战记之透明计算网络 评测结果 AAAAAAAAAA
题目名称 Asm_Def排兵布阵 最终得分 100
用户昵称 afo 运行时间 0.095 s
代码语言 C++ 内存使用 4.51 MiB
提交时间 2017-08-29 21:01:31
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long MOD=998244353;
long long func[500010];
int num[100010];
inline void exgcd(long long a,long long b,long long &d,long long &x,long long &y){
	if(!b){
		d=a;
		x=1;
		y=0;
	}
	else {
		exgcd(b,a%b,d,y,x);
		y-=(a/b)*x;
	}
}
int main(){
	freopen("asm_formation.in","r",stdin);
	freopen("asm_formation.out","w",stdout);
	int n;
	scanf("%d",&n);
	int sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
		sum+=num[i];
	}
	func[1]=1;
	for(int i=2;i<=sum;i++)
		func[i]=((func[i-1]%MOD)*(i%MOD))%MOD;
	long long ans=1;
	int now=num[1];
	for(int i=2;i<=n;i++){
		if(num[i]!=1){
			long long res=func[num[i]-1]*func[now];
			res%=MOD;
			long long tl=func[num[i]-1+now];
			long long x,y,d;
			exgcd(MOD,res,d,x,y);
			long long r=res/d,M=MOD/d;
			if(x>0){
				long long k=x/r;
				k++;
				y+=k*M;
				y%=MOD;
			}
			if(y<0){
				long long k=y/M;
				k++;
				y+=k*M;
				y%=MOD;
			}
			y*=tl;
			y%=MOD;
			ans=ans*y;
			ans%=MOD;
			//ans=(ans+MOD)%MOD;
		}
		now+=num[i];
	}
	cout<<ans<<endl;
return 0;
}