Submission #49547369

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=998244353;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}

ll fix(ll i){
	i%=MOD;
	if (i<0) i+=MOD;
	return i;
}

ll fac[1000005];
ll ifac[1000005];

ll nCk(int i,int j){
	if (i<j) return 0;
	return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD;
}

int n,m;
int arr[5005];

int memo[2][5005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	fac[0]=1;
	rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD;
	ifac[1000004]=inv(fac[1000004]);
	rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD;
	
	cin>>n>>m;
	rep(x,1,n+1) cin>>arr[x];
	
	int a=0,b=1;
	memo[a][0]=1;
	rep(x,1,n+1){
		memset(memo[b],0,sizeof(memo[b]));
		
		if (arr[x]==0){
			rep(y,0,x){
				memo[b][y]=(memo[b][y]+memo[a][y]*y)%MOD;
				memo[b][y+1]=(memo[b][y+1]+memo[a][y]*(m-y))%MOD;
			}
		}
		else{
			rep(y,0,x){
				memo[b][y+1]=memo[a][y];
			}
		}
		
		swap(a,b);
	}
	
	int ans=0;
	rep(x,0,min(n+1,m+2)) ans=(ans+memo[a][x])%MOD;
	cout<<ans<<endl;
}

Submission Info

Judge Result