提出 #68726202

---

ソースコード 拡げる

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

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using P=pair<int,int>;
using vi=vc<int>;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint& operator+=(const mint&r){return s(v+r.v);}
	mint&operator-=(const mint&r){return s(v+mod-r.v);}
	mint&operator*=(const mint&r){v=(unsigned long long)v*r.v%mod;return *this;}
	mint&operator/=(const mint&r){return *this*=r.inv();}
	mint operator+(const mint&r)const{return mint(*this)+=r;}
	mint operator-(const mint&r)const{return mint(*this)-=r;}
	mint operator*(const mint&r)const{return mint(*this)*=r;}
	mint operator/(const mint&r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};
#define SIZE 5005
mint inv[SIZE],fac[SIZE],finv[SIZE];
void make(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++){
		inv[i]=-inv[mod%i]*(mod/i);
		fac[i]=fac[i-1]*i;
		finv[i]=finv[i-1]*inv[i];
	}
}
mint C(int a,int b){
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]);
}

mint run(int n,int k,int x){
	if(x<0) return 0;
	mint ret=0;
	vc<vc<mint>> dp(k,vc<mint>(x+1));
	vc<mint> tw(k);
	tw[0]=1;
	for(int i=1;i<k;i++) tw[i]=tw[i-1]*2;
	for(int i=0;i<=2*x+1;i++){
		mint cur=C(i+n-1,i);
		if(i<x+1){
			mint zan=tw[k-1].pow(n);
			ret+=cur*zan;
		} else{
			dp[k-1][i-x-1]+=cur;
		}
	}
	for(int i=k-1;i>0;i--){
		mint zan=tw[i-1].pow(n);
		for(int j=0;j<=x;j++){
			for(int c=0;c<=n;c++){
				mint w=C(n,c)*dp[i][j];
				int nt=2*j+(c-x-1);
				if(nt<0){
					ret+=zan*w;
				} else if(nt<=x){
					dp[i-1][nt] += w;
				}
			}
		}
	}
	return ret;
}
void solve(){
	make();
	int n,k,x;
	cin>>n>>k>>x;
	mint ans=run(n,k,x) - run(n,k,x-1);
	cout<<ans.v<<endl;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int T=1;
	while(T--) solve();
}

提出情報

ジャッジ結果