QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#55378	#4807. Melborp Lacissalc	GZU_addd	AC ✓	250ms	86864kb	C++	2.1kb	2022-10-13 14:20:45	2022-10-13 14:22:05

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:22:05]
评测

测评结果：AC
用时：250ms
内存：86864kb

查看

[2022-10-13 14:20:45]
提交

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;
ll C[N][N];
ll Dp[N][N][N*N];
int main() {
	int n, k, t;
	cin >> n >> k >> t;
	for (int i = 0; i <= N-1; i ++ ) {
		for (int j = 0; j <= i; j ++ ) {
			if(!j) C[i][j] = 1;
			else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
		}
	}
	for (int j = 0; j <= 65; j ++ ) {
		Dp[0][j][(1+j)*j/2] = 1;
	}
	for (int i = 1; i <= k-1; i ++ ) {
		for (int j = 0; j <= n; j ++ ) {
			for (int cnt = 0; cnt <= j ; cnt ++ ) {
				for (int r = C[cnt][2]; r <= t; r ++ ) {
					(Dp[i][j][r] += Dp[i-1][j-cnt][r-C[cnt][2]]*C[j][cnt]) %= mod;
				}
			}
		}
	}
	cout << Dp[k-1][n][t];
	return 0;
}
//int main(){
//	cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
////	for(int T=read();T--;solve());
//	solve();
//}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 4036kb

input:

2 5 1

output:

result:

ok 1 number(s): "12"

Test #2:

score: 0

Accepted

time: 3ms

memory: 4104kb

input:

7 10 15

output:

result:

ok 1 number(s): "2016"

Test #3:

score: 0

Accepted

time: 11ms

memory: 16068kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

score: 0

Accepted

time: 3ms

memory: 20276kb

input:

64 64 0

output:

result:

ok 1 number(s): "0"

Test #5:

score: 0

Accepted

time: 3ms

memory: 20220kb

input:

64 64 1

output:

326126263

result:

ok 1 number(s): "326126263"

Test #6:

score: 0

Accepted

time: 13ms

memory: 20020kb

input:

63 64 0

output:

result:

ok 1 number(s): "4476118"

Test #7:

score: 0

Accepted

time: 2ms

memory: 6180kb

input:

11 45 14

output:

963276342

result:

ok 1 number(s): "963276342"

Test #8:

score: 0

Accepted

time: 4ms

memory: 9644kb

input:

35 20 565

output:

result:

ok 1 number(s): "0"

Test #9:

score: 0

Accepted

time: 0ms

memory: 4880kb

input:

3 64 5

output:

result:

ok 1 number(s): "0"

Test #10:

score: 0

Accepted

time: 2ms

memory: 12136kb

input:

35 45 153

output:

181934997

result:

ok 1 number(s): "181934997"

Test #11:

score: 0

Accepted

time: 0ms

memory: 4192kb

input:

3 25 5

output:

result:

ok 1 number(s): "0"

Test #12:

score: 0

Accepted

time: 4ms

memory: 5040kb

input:

35 5 373

output:

740122840

result:

ok 1 number(s): "740122840"

Test #13:

score: 0

Accepted

time: 2ms

memory: 4736kb

input:

3 50 5

output:

result:

ok 1 number(s): "0"

Test #14:

score: 0

Accepted

time: 10ms

memory: 12964kb

input:

35 30 592

output:

result:

ok 1 number(s): "0"

Test #15:

score: 0

Accepted

time: 2ms

memory: 4056kb

input:

3 11 1

output:

result:

ok 1 number(s): "540"

Test #16:

score: 0

Accepted

time: 12ms

memory: 17064kb

input:

35 55 352

output:

656633208

result:

ok 1 number(s): "656633208"

Test #17:

score: 0

Accepted

time: 14ms

memory: 17700kb

input:

54 38 356

output:

215089708

result:

ok 1 number(s): "215089708"

Test #18:

score: 0

Accepted

time: 2ms

memory: 6160kb

input:

22 19 189

output:

result:

ok 1 number(s): "0"

Test #19:

score: 0

Accepted

time: 29ms

memory: 28180kb

input:

54 63 401

output:

987604839

result:

ok 1 number(s): "987604839"

Test #20:

score: 0

Accepted

time: 8ms

memory: 9112kb

input:

22 43 171

output:

827743481

result:

ok 1 number(s): "827743481"

Test #21:

score: 0

Accepted

time: 11ms

memory: 13312kb

input:

54 24 446

output:

551546514

result:

ok 1 number(s): "551546514"

Test #22:

score: 0

Accepted

time: 3ms

memory: 4336kb

input:

22 4 152

output:

result:

ok 1 number(s): "0"

Test #23:

score: 0

Accepted

time: 99ms

memory: 40692kb

input:

54 48 1306

output:

result:

ok 1 number(s): "0"

Test #24:

score: 0

Accepted

time: 1ms

memory: 6424kb

input:

22 29 7

output:

374430631

result:

ok 1 number(s): "374430631"

Test #25:

score: 0

Accepted

time: 18ms

memory: 10264kb

input:

54 9 1351

output:

result:

ok 1 number(s): "0"

Test #26:

score: 0

Accepted

time: 0ms

memory: 8680kb

input:

22 54 5

output:

267958047

result:

ok 1 number(s): "267958047"

Test #27:

score: 0

Accepted

time: 68ms

memory: 32640kb

input:

64 32 1315

output:

494251101

result:

ok 1 number(s): "494251101"

Test #28:

score: 0

Accepted

time: 0ms

memory: 6332kb

input:

33 12 332

output:

765350074

result:

ok 1 number(s): "765350074"

Test #29:

score: 0

Accepted

time: 2ms

memory: 4428kb

input:

1 57 1

output:

result:

ok 1 number(s): "1"

Test #30:

score: 0

Accepted

time: 12ms

memory: 12252kb

input:

33 37 363

output:

result:

ok 1 number(s): "0"

Test #31:

score: 0

Accepted

time: 2ms

memory: 3976kb

input:

1 17 0

output:

result:

ok 1 number(s): "16"

Test #32:

score: 0

Accepted

time: 3ms

memory: 14548kb

input:

33 62 148

output:

871819399

result:

ok 1 number(s): "871819399"

Test #33:

score: 0

Accepted

time: 3ms

memory: 4216kb

input:

1 42 0

output:

result:

ok 1 number(s): "41"

Test #34:

score: 0

Accepted

time: 2ms

memory: 7976kb

input:

33 23 179

output:

23699248

result:

ok 1 number(s): "23699248"

Test #35:

score: 0

Accepted

time: 2ms

memory: 3884kb

input:

1 3 1

output:

result:

ok 1 number(s): "1"

Test #36:

score: 0

Accepted

time: 10ms

memory: 12712kb

input:

33 47 211

output:

267909794

result:

ok 1 number(s): "267909794"

Test #37:

score: 0

Accepted

time: 2ms

memory: 5160kb

input:

11 26 32

output:

result:

ok 1 number(s): "0"

Test #38:

score: 0

Accepted

time: 0ms

memory: 5716kb

input:

43 6 579

output:

280289125

result:

ok 1 number(s): "280289125"

Test #39:

score: 0

Accepted

time: 2ms

memory: 6244kb

input:

11 50 5

output:

865381083

result:

ok 1 number(s): "865381083"

Test #40:

score: 0

Accepted

time: 25ms

memory: 16852kb

input:

43 31 750

output:

result:

ok 1 number(s): "0"

Test #41:

score: 0

Accepted

time: 3ms

memory: 4512kb

input:

11 11 12

output:

753565341

result:

ok 1 number(s): "753565341"

Test #42:

score: 0

Accepted

time: 18ms

memory: 19008kb

input:

43 56 290

output:

575236094

result:

ok 1 number(s): "575236094"

Test #43:

score: 0

Accepted

time: 5ms

memory: 5824kb

input:

11 36 52

output:

result:

ok 1 number(s): "0"

Test #44:

score: 0

Accepted

time: 2ms

memory: 6520kb

input:

44 16 0

output:

result:

ok 1 number(s): "0"

Test #45:

score: 0

Accepted

time: 0ms

memory: 7072kb

input:

12 61 31

output:

682427534

result:

ok 1 number(s): "682427534"

Test #46:

score: 0

Accepted

time: 9ms

memory: 16196kb

input:

44 41 365

output:

759457870

result:

ok 1 number(s): "759457870"

Test #47:

score: 0

Accepted

time: 2ms

memory: 5612kb

input:

22 19 70

output:

247296498

result:

ok 1 number(s): "247296498"

Test #48:

score: 0

Accepted

time: 39ms

memory: 29756kb

input:

54 64 444

output:

418216086

result:

ok 1 number(s): "418216086"

Test #49:

score: 0

Accepted

time: 0ms

memory: 8408kb

input:

22 44 52

output:

779702126

result:

ok 1 number(s): "779702126"

Test #50:

score: 0

Accepted

time: 39ms

memory: 22716kb

input:

54 25 1303

output:

result:

ok 1 number(s): "0"

Test #51:

score: 0

Accepted

time: 3ms

memory: 4236kb

input:

22 5 49

output:

219556981

result:

ok 1 number(s): "219556981"

Test #52:

score: 0

Accepted

time: 80ms

memory: 40680kb

input:

54 49 1269

output:

result:

ok 1 number(s): "0"

Test #53:

score: 0

Accepted

time: 2ms

memory: 6628kb

input:

22 30 14

output:

719775605

result:

ok 1 number(s): "719775605"

Test #54:

score: 0

Accepted

time: 14ms

memory: 11012kb

input:

54 10 1314

output:

result:

ok 1 number(s): "0"

Test #55:

score: 0

Accepted

time: 0ms

memory: 8892kb

input:

22 54 12

output:

325137058

result:

ok 1 number(s): "325137058"

Test #56:

score: 0

Accepted

time: 65ms

memory: 31296kb

input:

54 35 1359

output:

result:

ok 1 number(s): "0"

Test #57:

score: 0

Accepted

time: 2ms

memory: 6728kb

input:

33 13 335

output:

202725820

result:

ok 1 number(s): "202725820"

Test #58:

score: 0

Accepted

time: 250ms

memory: 86864kb

input:

64 64 2080

output:

result:

ok 1 number(s): "1"

Test #59:

score: 0

Accepted

time: 2ms

memory: 3988kb

input:

1 1 0

output:

result:

ok 1 number(s): "0"

Test #60:

score: 0

Accepted

time: 2ms

memory: 3892kb

input:

1 1 1

output:

result:

ok 1 number(s): "1"

Test #61:

score: 0

Accepted

time: 240ms

memory: 82388kb

input:

63 63 2016

output:

result:

ok 1 number(s): "1"