QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55372#4807. Melborp LacissalcGZU_adddWA 7ms20340kbC++2.2kb2022-10-13 14:08:522022-10-13 14:08:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-13 14:08:54]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:20340kb
  • [2022-10-13 14:08:52]
  • 提交

answer

#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define pb push_back
#define pq priority_queue
#define vt vector
#define lb(x) (x&-x)
#define sub(i,j) ((1LL*i-1LL*j)%k+k)%k
std::mt19937 rnd(233);
using namespace std;
using ll=long long;
//using node=pair<int,int>;
//using nnode=array<int,3>;
//inline int read(){
//	int x=0,f=1;
//	char c=getchar();
//	while(c<'0'||c>'9'){
//		if(c=='-') f=-1;
//		c=getchar();
//	}
//	while(c>='0'&&c<='9'){
//		x=x*10+(c^'0');
//		c=getchar();
//	}
//	return x*f;
//}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>auto min(U x,V y){return x<y?x:y;}
template<typename U,typename V>auto max(U x,V y){return x>y?x:y;}
template<typename U,typename...V>auto min(U x,V...y){return min(x,min(y...));}
template<typename U,typename...V>auto max(U x,V...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,V y){return x>y?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,V y){return x<y?x=y,true:false;}
constexpr int mod=998244353;
ll qpow(int x,int n=mod-2){ll y=1;for(;n;n>>=1,x=1LL*x*x%mod)if(n&1)y=1LL*y*x%mod;return y;}
//inline ll qpow(ll a, ll n=mod-2) { ll ans = 1;    while (n) { if (n & 1) { ans *= a; }a *= a; n >>= 1; }return ans; }
constexpr int N=65,M=N*(N+1)/2;
constexpr ll inf=1e18;
int n,m,k,fac[N],infac[N],f[N][N][M];
int C(int x,int y){if(x<y)return 0;return 1LL*fac[x]*infac[y]%mod*infac[x-y]%mod;}
void solve(){
	cin>>n>>k>>m;
	f[0][0][0]=fac[0]=1;
	for(int i=1;i<=n;++i)fac[i]=1LL*fac[i-1]*i%mod;
	infac[n]=qpow(fac[n]);
	for(int i=n-1;~i;--i)infac[i]=1LL*infac[i+1]*(i+1)%mod;
	for(int i=1;i<=k;++i){
		for(int j=1;j<=n;++j){
			for(int l=1;l<=j;++l){
				int del;
				if(i==1)del=C(l+1,2);
				else del=C(l,2);
				for(int p=del;p<=m;++p)
					f[i][j][p]=(f[i][j][p]+1LL*f[i-1][j-l][p-del]*C(j,l)%mod)%mod;
			}
		}
		for(int j=0;j<=n;++j)for(int p=0;p<=m;++p)
			f[i][j][p]=(f[i][j][p]+f[i-1][j][p])%mod;
	}
	if(m==0)cout<<f[k][n][m]-1;
	else cout<<f[k][n][m];
}
int main(){
	cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//	for(int T=read();T--;solve());
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3812kb

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

score: 0
Accepted
time: 7ms
memory: 14552kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 20340kb

input:

64 64 0

output:

-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'