Submission #42726804

---

Source Code Expand

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
template<typename T>void ckmn(T&a,T b){a=min(a,b);}
template<typename T>void ckmx(T&a,T b){a=max(a,b);}
void rd(int&x){scanf("%i",&x);}
void rd(ll&x){scanf("%lld",&x);}
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;}
int ri(){int x;rd(x);return x;}
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;}
template<typename T>void ra(T a[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]);}
template<typename T1,typename T2>void ra(T1 a[],T2 b[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]);}
template<typename T1,typename T2,typename T3>void ra(T1 a[],T2 b[],T3 c[],int n,int st=1){for(int i=0;i<n;++i)rd(a[st+i]),rd(b[st+i]),rd(c[st+i]);}
void re(vector<int> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){rd(u,v);E[u].pb(v);if(!dir)E[v].pb(u);}}
template<typename T>void re(vector<pair<int,T>> E[],int m,bool dir=0){for(int i=0,u,v;i<m;++i){T w;rd(u,v,w);E[u].pb({v,w});if(!dir)E[v].pb({u,w});}}

const int mod=998244353;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
void ckadd(int&a,int b){a=add(a,b);}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
void cksub(int&a,int b){a=sub(a,b);}
int mul(int a,int b){return (ll)a*b%mod;}
void ckmul(int&a,int b){a=mul(a,b);}
int powmod(int x,int k){int ans=1;for(;k;k>>=1,ckmul(x,x))if(k&1)ckmul(ans,x);return ans;}
int inv(int x){return powmod(x,mod-2);}

const int N=505;
int F[N],I[N];
int binom(int n, int k){
	if(n<k||k<0)return 0;
	return mul(F[n],mul(I[k],I[n-k]));
}
void calc()
{
	F[0]=1;
	for(int i=1;i<N;i++) F[i]=mul(F[i-1],i);
	I[N-1]=inv(F[N-1]);
	for(int i=N-2;~i;i--) I[i]=mul(I[i+1],i+1);
}

//pair<int,int> dp[N];
int dp[N][N],nxt[N][N];
int d[N],psum[N];
int fw[N];
int main(){
	calc();

	int n=ri();
	for(int i=1;i<=n;i++){
		rd(d[i]);
	}
	d[1]--;
	fw[0]=1;
	for(int i=1;i<=n;i++){
		psum[i]=psum[i-1]+d[i];
		fw[i]=mul(fw[i-1],binom(psum[i],d[i]));
	}

	dp[0][0]=1;
	int sm=0,tot=0;

	//printf("trees:%i\n",fw[n]);

	int ans=fw[n];
	for(int i=n;i>=2;i--){
		if(d[i]==0){
			ckadd(ans,fw[n]);
			//printf("i:%i leaf add:%i\n",i,fw[n]);
		}else{
			for(int j=0;j<=sm;j++){
				for(int c=0;c<=tot;c++){
					if(j+d[i]-1 == (c+1)-2){
						//int was=ans;
						ckadd(ans,mul(mul(dp[j][c],binom((c+1)-2,d[i]-1)),mul(fw[i-1],binom(psum[i-1]+sm-j,psum[i-1]))));
						//printf("i:%i j:%i c:%i add:%i\n",i,j,c,ans-was);
					}
				}
			}
		}

		sm+=d[i];
		tot++;
		for(int j=0;j<=sm;j++){
			for(int c=0;c<=tot;c++){
				ckadd(nxt[j][c],mul(dp[j][c],binom(sm-j,d[i])));
				if(j+d[i]<=sm && c+1<=tot){
					ckadd(nxt[j+d[i]][c+1],mul(dp[j][c],binom(j+d[i],d[i])));
				}
			}
		}

		for(int j=0;j<=sm;j++){
			for(int c=0;c<=tot;c++){
				dp[j][c]=nxt[j][c];
				nxt[j][c]=0;
			}
		}
	}
	printf("%i\n",ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void rd(std::string&)’:
./Main.cpp:17:27: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘std::string*’ {aka ‘std::__cxx11::basic_string<char>*’} [-Wformat=]
   17 | void rd(string&x){scanf("%s",&x);}
      |                          ~^  ~~
      |                           |  |
      |                           |  std::string* {aka std::__cxx11::basic_string<char>*}
      |                           char*
./Main.cpp: In function ‘void rd(int&)’:
./Main.cpp:13:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   13 | void rd(int&x){scanf("%i",&x);}
      |                ~~~~~^~~~~~~~~
./Main.cpp: In function ‘void rd(long long int&)’:
./Main.cpp:14:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   14 | void rd(ll&x){scanf("%lld",&x);}
      |               ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘void rd(char*)’:
./Main.cpp:15:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   15 | void rd(char*x){scanf("%s",x);}
      |                 ~~~~~^~~~~~~~
./Main.cpp: In function ‘void rd(double&)’:
./Main.cpp:16:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   16 | void rd(ldb&x){scanf("%lf",&x);}
      |                ~~~~~^~~~~~~~~~
./Main.cpp: In function ‘void rd(std::string&)’:
./Main.cpp:17:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   17 | void rd(string&x){scanf("%s",&x);}
      |                   ~~~~~^~~~~~~~~

Judge Result