QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397288#8116. Kockelfxxx#80 104ms22384kbC++141.2kb2024-04-23 21:28:172024-07-04 03:37:11

Judging History

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

  • [2024-07-04 03:37:11]
  • 评测
  • 测评结果:80
  • 用时:104ms
  • 内存:22384kb
  • [2024-04-23 21:28:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 5005, mod = 1e9 + 7;
int n, k, f[N][N][2];
bool en;
int main()
{
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n-------------------\n";
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	f[2][n - 1][0] = f[2][n - 1][1] = 1;
	int ans = 2 * (k - 1);
	for (int i = 3; i <= min(n, k); ++i) {
		for (int j = n - i + 1; j >= 1; --j) {
			f[i][j][0] = f[i][j][1] = 0;
			for (int k = 0; j + 1 + 2 * k <= n; ++k) {
				f[i][j][0] = (f[i][j][0] + f[i - 1][j + 1 + 2 * k][0]) % mod;
				f[i][j][1] = (f[i][j][1] + f[i - 1][j + 1 + 2 * k][1]) % mod;
			}
			for (int k = 0; i + j - 1 + 2 * k <= n; ++k) {
				f[i][j][0] = (f[i][j][0] + f[i - 1][i + j - 1 + 2 * k][1]) % mod;
				f[i][j][1] = (f[i][j][1] + f[i - 1][i + j - 1 + 2 * k][0]) % mod;
			}
			ans = (ans + (ll) (f[i][j][0] + f[i][j][1]) * (k - i + 1)) % mod;
		}
	}
	cout << ans << endl;
	return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1ms
memory: 3520kb

input:

2 3

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

5 18

output:

218

result:

ok single line: '218'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

9 18

output:

1980

result:

ok single line: '1980'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

15 9

output:

9564

result:

ok single line: '9564'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

16 18

output:

66116

result:

ok single line: '66116'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

18 10

output:

43140

result:

ok single line: '43140'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

18 18

output:

170888

result:

ok single line: '170888'

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #8:

score: 30
Accepted
time: 1ms
memory: 3692kb

input:

2 49

output:

96

result:

ok single line: '96'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

7 38

output:

1598

result:

ok single line: '1598'

Test #10:

score: 0
Accepted
time: 1ms
memory: 5680kb

input:

19 6

output:

5524

result:

ok single line: '5524'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

31 49

output:

369127208

result:

ok single line: '369127208'

Test #12:

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

input:

44 30

output:

310756420

result:

ok single line: '310756420'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

49 2

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

50 50

output:

375733561

result:

ok single line: '375733561'

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #15:

score: 30
Accepted
time: 1ms
memory: 3716kb

input:

2 319

output:

636

result:

ok single line: '636'

Test #16:

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

input:

89 44

output:

999831996

result:

ok single line: '999831996'

Test #17:

score: 0
Accepted
time: 17ms
memory: 13920kb

input:

280 279

output:

332244975

result:

ok single line: '332244975'

Test #18:

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

input:

282 500

output:

344135056

result:

ok single line: '344135056'

Test #19:

score: 0
Accepted
time: 63ms
memory: 11908kb

input:

464 211

output:

629248621

result:

ok single line: '629248621'

Test #20:

score: 0
Accepted
time: 104ms
memory: 22384kb

input:

499 500

output:

732883324

result:

ok single line: '732883324'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

500 2

output:

2

result:

ok single line: '2'

Test #22:

score: 0
Accepted
time: 90ms
memory: 16108kb

input:

500 324

output:

992004807

result:

ok single line: '992004807'

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #23:

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

input:

2 4999

output:

9996

result:

ok single line: '9996'

Test #24:

score: -30
Time Limit Exceeded

input:

1988 4702

output:


result: