QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55376#4807. Melborp LacissalcGZU_adddWA 163ms26128kbC++2.2kb2022-10-13 14:14:202022-10-13 14:14:24

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:14:24]
  • 评测
  • 测评结果:WA
  • 用时:163ms
  • 内存:26128kb
  • [2022-10-13 14:14:20]
  • 提交

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;
	}
	cout<<max(0,f[k][n][m]-!m);
}
int main(){
	cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//	for(int T=read();T--;solve());
	solve();
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5644kb

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 3ms
memory: 5856kb

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

score: 0
Accepted
time: 15ms
memory: 15836kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

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

input:

64 64 0

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

64 64 1

output:

326126263

result:

ok 1 number(s): "326126263"

Test #6:

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

input:

63 64 0

output:

4476118

result:

ok 1 number(s): "4476118"

Test #7:

score: 0
Accepted
time: 5ms
memory: 7652kb

input:

11 45 14

output:

963276342

result:

ok 1 number(s): "963276342"

Test #8:

score: 0
Accepted
time: 18ms
memory: 9308kb

input:

35 20 565

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 3ms
memory: 6688kb

input:

3 64 5

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 13ms
memory: 12484kb

input:

35 45 153

output:

181934997

result:

ok 1 number(s): "181934997"

Test #11:

score: 0
Accepted
time: 0ms
memory: 6000kb

input:

3 25 5

output:

0

result:

ok 1 number(s): "0"

Test #12:

score: 0
Accepted
time: 5ms
memory: 6156kb

input:

35 5 373

output:

740122840

result:

ok 1 number(s): "740122840"

Test #13:

score: 0
Accepted
time: 3ms
memory: 6480kb

input:

3 50 5

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 22ms
memory: 11632kb

input:

35 30 592

output:

0

result:

ok 1 number(s): "0"

Test #15:

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

input:

3 11 1

output:

540

result:

ok 1 number(s): "540"

Test #16:

score: 0
Accepted
time: 29ms
memory: 15792kb

input:

35 55 352

output:

656633208

result:

ok 1 number(s): "656633208"

Test #17:

score: 0
Accepted
time: 30ms
memory: 15872kb

input:

54 38 356

output:

215089708

result:

ok 1 number(s): "215089708"

Test #18:

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

input:

22 19 189

output:

0

result:

ok 1 number(s): "0"

Test #19:

score: 0
Accepted
time: 58ms
memory: 23724kb

input:

54 63 401

output:

987604839

result:

ok 1 number(s): "987604839"

Test #20:

score: 0
Accepted
time: 5ms
memory: 10196kb

input:

22 43 171

output:

827743481

result:

ok 1 number(s): "827743481"

Test #21:

score: 0
Accepted
time: 15ms
memory: 12188kb

input:

54 24 446

output:

551546514

result:

ok 1 number(s): "551546514"

Test #22:

score: 0
Accepted
time: 3ms
memory: 5768kb

input:

22 4 152

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 163ms
memory: 26128kb

input:

54 48 1306

output:

0

result:

ok 1 number(s): "0"

Test #24:

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

input:

22 29 7

output:

374430631

result:

ok 1 number(s): "374430631"

Test #25:

score: 0
Accepted
time: 34ms
memory: 8048kb

input:

54 9 1351

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

22 54 5

output:

267958047

result:

ok 1 number(s): "267958047"

Test #27:

score: 0
Accepted
time: 133ms
memory: 20996kb

input:

64 32 1315

output:

494251101

result:

ok 1 number(s): "494251101"

Test #28:

score: 0
Accepted
time: 8ms
memory: 7208kb

input:

33 12 332

output:

765350074

result:

ok 1 number(s): "765350074"

Test #29:

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

input:

1 57 1

output:

0

result:

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