QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295957#4893. Imbalancezyc07041920 1795ms53072kbC++141.8kb2024-01-01 19:27:192024-01-01 19:27:19

Judging History

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

  • [2024-01-01 19:27:19]
  • 评测
  • 测评结果:20
  • 用时:1795ms
  • 内存:53072kb
  • [2024-01-01 19:27:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;

inline int add(int x, int y) {x += y; return x >= mod ? x - mod : x;}
inline int del(int x, int y) {x -= y; return x < 0 ? x + mod : x;}
inline void Add(int &x, int y) {x = add(x, y);}
inline void Del(int &x, int y) {x = del(x, y);}

int n, k, m, a[200];
char s[200];

namespace subtask1 {
	int dp[2][(1 << 22) + 3], opt, ans, cnt[(1 << 22) + 3];
	
	void work() {
		memset(dp, 0, sizeof(dp));
		dp[opt][0] = 1;
		for (int i = 1; i <= n; ++i) {
			opt ^= 1;
			for (int S = 0; S < (1 << k); ++S) dp[opt][S] = 0;
			for (int S = 0, T; S < (1 << k); ++S) {
				if (cnt[S] >= (k / 2)) continue;
				if (i > m || a[i] == 0) {
					T = (S >> 1);
					Add(dp[opt][T], dp[opt ^ 1][S]);
				}
				if (i > m || a[i] == 1) {
					T = (S >> 1) | (1 << (k - 1));
					if (cnt[T] >= (k / 2)) continue;
					Add(dp[opt][T], dp[opt ^ 1][S]);
				}
			}
		}
		for (int S = 0; S < (1 << k); ++S) Add(ans, dp[opt][S]);
	}
	
	void solve() {
		for (int i = 1; i < (1 << k); ++i) cnt[i] = cnt[i ^ (i & -i)] + 1;
		work();
		for (int i = 1; i <= m; ++i) a[i] ^= 1;
		work();
		printf("%d\n", ans);
	}
}

namespace subtask2 {
	const int Mod = 2997;
	struct Hash_Table {
		struct node {
			vector<int> id;
			int val;
		};
		vector<int> q;
		
		
	};
	int st[10], mx, opt;
	
	void work() {
		
	}
	
	void dfs(int t, int lst) {
		if (t > mx) return work(), void();
		for (int i = lst; i < lst + k / 2; ++i) {
			st[t] = i;
			dfs(t + 1, i);
		}
	}
	
	void solve() {
		mx = n / k;
		dfs(1, 0);
		for (int i = 1; i <= m; ++i) a[i] ^= 1;
		dfs(1, 0);
	}
}

int main() {
	scanf("%d%d%d%s", &n, &k, &m, s + 1);
	for (int i = 1; i <= m; ++i) a[i] = s[i] - '0';
	if (k <= 22) subtask1 :: solve();
	else if (n <= 66) subtask2 :: solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 6ms
memory: 38392kb

input:

2 2 0

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

2 2 1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

3 2 0

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

3 2 1
0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

4 2 0

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

4 2 1
0

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

input:

4 4 0

output:

10

result:

ok 1 number(s): "10"

Test #8:

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

input:

4 4 1
1

output:

5

result:

ok 1 number(s): "5"

Test #9:

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

input:

4 4 2
00

output:

3

result:

ok 1 number(s): "3"

Test #10:

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

input:

4 4 3
101

output:

1

result:

ok 1 number(s): "1"

Test #11:

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

input:

5 2 0

output:

2

result:

ok 1 number(s): "2"

Test #12:

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

input:

5 2 1
1

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 4ms
memory: 37848kb

input:

5 4 0

output:

14

result:

ok 1 number(s): "14"

Test #14:

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

input:

5 4 1
0

output:

7

result:

ok 1 number(s): "7"

Test #15:

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

input:

5 4 2
01

output:

3

result:

ok 1 number(s): "3"

Test #16:

score: 0
Accepted
time: 4ms
memory: 37584kb

input:

5 4 3
110

output:

1

result:

ok 1 number(s): "1"

Test #17:

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

input:

17 2 0

output:

2

result:

ok 1 number(s): "2"

Test #18:

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

input:

17 2 0

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

17 10 6
110111

output:

621

result:

ok 1 number(s): "621"

Test #20:

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

input:

17 10 2
11

output:

8413

result:

ok 1 number(s): "8413"

Test #21:

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

input:

18 2 1
1

output:

1

result:

ok 1 number(s): "1"

Test #22:

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

input:

18 2 1
1

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 4ms
memory: 37160kb

input:

18 8 5
00010

output:

918

result:

ok 1 number(s): "918"

Test #24:

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

input:

18 8 3
001

output:

3404

result:

ok 1 number(s): "3404"

Test #25:

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

input:

18 16 6
100011

output:

2458

result:

ok 1 number(s): "2458"

Test #26:

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

input:

18 16 8
00101101

output:

548

result:

ok 1 number(s): "548"

Test #27:

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

input:

19 2 1
1

output:

1

result:

ok 1 number(s): "1"

Test #28:

score: 0
Accepted
time: 6ms
memory: 37136kb

input:

19 2 0

output:

2

result:

ok 1 number(s): "2"

Test #29:

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

input:

19 6 2
00

output:

3413

result:

ok 1 number(s): "3413"

Test #30:

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

input:

19 6 1
1

output:

7012

result:

ok 1 number(s): "7012"

Test #31:

score: 0
Accepted
time: 4ms
memory: 37796kb

input:

19 12 10
1010110000

output:

266

result:

ok 1 number(s): "266"

Test #32:

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

input:

19 12 3
111

output:

19234

result:

ok 1 number(s): "19234"

Test #33:

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

input:

19 16 2
10

output:

77876

result:

ok 1 number(s): "77876"

Test #34:

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

input:

19 16 0

output:

301208

result:

ok 1 number(s): "301208"

Test #35:

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

input:

20 2 1
0

output:

1

result:

ok 1 number(s): "1"

Test #36:

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

input:

20 2 0

output:

2

result:

ok 1 number(s): "2"

Test #37:

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

input:

20 10 9
110111000

output:

76

result:

ok 1 number(s): "76"

Test #38:

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

input:

20 10 9
110101110

output:

372

result:

ok 1 number(s): "372"

Test #39:

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

input:

20 14 11
10110110000

output:

207

result:

ok 1 number(s): "207"

Test #40:

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

input:

20 14 7
0011011

output:

3675

result:

ok 1 number(s): "3675"

Test #41:

score: 0
Accepted
time: 76ms
memory: 42832kb

input:

20 20 14
10111010000000

output:

58

result:

ok 1 number(s): "58"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #42:

score: 10
Accepted
time: 4ms
memory: 37956kb

input:

114 12 11
11010000010

output:

394940507

result:

ok 1 number(s): "394940507"

Test #43:

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

input:

114 12 2
01

output:

60509873

result:

ok 1 number(s): "60509873"

Test #44:

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

input:

114 14 10
1001111011

output:

154687039

result:

ok 1 number(s): "154687039"

Test #45:

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

input:

114 14 5
00100

output:

941826071

result:

ok 1 number(s): "941826071"

Test #46:

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

input:

114 16 10
1011101001

output:

391666362

result:

ok 1 number(s): "391666362"

Test #47:

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

input:

114 16 15
000010011111010

output:

599226561

result:

ok 1 number(s): "599226561"

Test #48:

score: 0
Accepted
time: 70ms
memory: 38636kb

input:

114 18 1
0

output:

167675624

result:

ok 1 number(s): "167675624"

Test #49:

score: 0
Accepted
time: 72ms
memory: 40616kb

input:

114 18 8
11000001

output:

165986235

result:

ok 1 number(s): "165986235"

Test #50:

score: 0
Accepted
time: 763ms
memory: 42832kb

input:

114 20 17
11101000010011010

output:

852476378

result:

ok 1 number(s): "852476378"

Test #51:

score: 0
Accepted
time: 782ms
memory: 42732kb

input:

114 20 13
1101011010000

output:

974712368

result:

ok 1 number(s): "974712368"

Test #52:

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

input:

113 12 8
10101100

output:

754580060

result:

ok 1 number(s): "754580060"

Test #53:

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

input:

113 12 10
1110010010

output:

928476173

result:

ok 1 number(s): "928476173"

Test #54:

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

input:

113 14 9
010111000

output:

930953494

result:

ok 1 number(s): "930953494"

Test #55:

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

input:

113 14 0

output:

613264431

result:

ok 1 number(s): "613264431"

Test #56:

score: 0
Accepted
time: 24ms
memory: 38152kb

input:

113 16 4
0011

output:

966491874

result:

ok 1 number(s): "966491874"

Test #57:

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

input:

113 16 10
1110110011

output:

71975445

result:

ok 1 number(s): "71975445"

Test #58:

score: 0
Accepted
time: 74ms
memory: 40792kb

input:

113 18 2
01

output:

35416931

result:

ok 1 number(s): "35416931"

Test #59:

score: 0
Accepted
time: 80ms
memory: 40788kb

input:

113 18 11
01101011111

output:

605684813

result:

ok 1 number(s): "605684813"

Test #60:

score: 0
Accepted
time: 835ms
memory: 42776kb

input:

113 20 1
1

output:

970488755

result:

ok 1 number(s): "970488755"

Test #61:

score: 0
Accepted
time: 750ms
memory: 42672kb

input:

113 20 17
10000001101111001

output:

308768022

result:

ok 1 number(s): "308768022"

Test #62:

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

input:

112 12 10
1011100000

output:

379472486

result:

ok 1 number(s): "379472486"

Test #63:

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

input:

112 12 3
111

output:

876338776

result:

ok 1 number(s): "876338776"

Test #64:

score: 0
Accepted
time: 4ms
memory: 37900kb

input:

112 14 6
100111

output:

850899867

result:

ok 1 number(s): "850899867"

Test #65:

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

input:

112 14 11
11011001011

output:

579315503

result:

ok 1 number(s): "579315503"

Test #66:

score: 0
Accepted
time: 19ms
memory: 40784kb

input:

112 16 11
00000111111

output:

827780781

result:

ok 1 number(s): "827780781"

Test #67:

score: 0
Accepted
time: 19ms
memory: 40788kb

input:

112 16 9
101001101

output:

247916257

result:

ok 1 number(s): "247916257"

Test #68:

score: 0
Accepted
time: 71ms
memory: 40784kb

input:

112 18 16
0011000001111001

output:

740632908

result:

ok 1 number(s): "740632908"

Test #69:

score: 0
Accepted
time: 76ms
memory: 38244kb

input:

112 18 4
0010

output:

594108528

result:

ok 1 number(s): "594108528"

Test #70:

score: 0
Accepted
time: 796ms
memory: 42640kb

input:

112 20 7
1010100

output:

818166882

result:

ok 1 number(s): "818166882"

Test #71:

score: 0
Accepted
time: 747ms
memory: 42672kb

input:

112 20 16
0001100100101000

output:

222914924

result:

ok 1 number(s): "222914924"

Test #72:

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

input:

111 12 2
11

output:

895626591

result:

ok 1 number(s): "895626591"

Test #73:

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

input:

111 12 1
1

output:

543447881

result:

ok 1 number(s): "543447881"

Test #74:

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

input:

111 14 3
111

output:

555958815

result:

ok 1 number(s): "555958815"

Test #75:

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

input:

111 14 13
1110001101010

output:

47749667

result:

ok 1 number(s): "47749667"

Test #76:

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

input:

111 16 5
01000

output:

880732287

result:

ok 1 number(s): "880732287"

Test #77:

score: 0
Accepted
time: 21ms
memory: 37560kb

input:

111 16 7
0110010

output:

153134396

result:

ok 1 number(s): "153134396"

Test #78:

score: 0
Accepted
time: 75ms
memory: 37932kb

input:

111 18 17
11011101001111100

output:

718197735

result:

ok 1 number(s): "718197735"

Test #79:

score: 0
Accepted
time: 73ms
memory: 40628kb

input:

111 18 9
011110101

output:

78875109

result:

ok 1 number(s): "78875109"

Test #80:

score: 0
Accepted
time: 795ms
memory: 42828kb

input:

111 20 6
100101

output:

484008568

result:

ok 1 number(s): "484008568"

Test #81:

score: 0
Accepted
time: 725ms
memory: 42736kb

input:

111 20 19
1100110110001010110

output:

612558978

result:

ok 1 number(s): "612558978"

Test #82:

score: 0
Accepted
time: 714ms
memory: 42660kb

input:

102 20 10
0101000100

output:

678899105

result:

ok 1 number(s): "678899105"

Test #83:

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

input:

97 16 13
0101110011010

output:

456291266

result:

ok 1 number(s): "456291266"

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #84:

score: 30
Accepted
time: 470ms
memory: 42676kb

input:

66 20 5
11001

output:

286180948

result:

ok 1 number(s): "286180948"

Test #85:

score: 0
Accepted
time: 390ms
memory: 42832kb

input:

66 20 19
0101001111011100100

output:

334317215

result:

ok 1 number(s): "334317215"

Test #86:

score: 0
Accepted
time: 1604ms
memory: 53020kb

input:

66 22 19
1001101100000100001

output:

465510840

result:

ok 1 number(s): "465510840"

Test #87:

score: 0
Accepted
time: 1795ms
memory: 53072kb

input:

66 22 11
10001111000

output:

731812403

result:

ok 1 number(s): "731812403"

Test #88:

score: -30
Wrong Answer
time: 0ms
memory: 3548kb

input:

66 24 6
011111

output:


result:

wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

Subtask #4:

score: 0
Time Limit Exceeded

Test #137:

score: 20
Accepted
time: 849ms
memory: 42696kb

input:

114 20 0

output:

849724285

result:

ok 1 number(s): "849724285"

Test #138:

score: -20
Time Limit Exceeded

input:

114 22 0

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #3:

0%