QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397299#8116. Kockelfxxx#110 ✓68ms168568kbC++14904b2024-04-23 21:43:032024-07-04 03:37:12

Judging History

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

  • [2024-07-04 03:37:12]
  • 评测
  • 测评结果:110
  • 用时:68ms
  • 内存:168568kb
  • [2024-04-23 21:43:03]
  • 提交

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], sum[N][N];
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] = 1;
	for (int i = n - 1; i >= 1; i -= 2) sum[2][i] = 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] = (sum[i - 1][j + 1] + sum[i - 1][i + j - 1]) % mod;
			ans = (ans + (ll) (f[i][j] * 2) * (k - i + 1)) % mod;
			sum[i][j] = (sum[i][j + 2] + f[i][j]) % mod;
		}
	}
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

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

input:

2 3

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5 18

output:

218

result:

ok single line: '218'

Test #3:

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

input:

9 18

output:

1980

result:

ok single line: '1980'

Test #4:

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

input:

15 9

output:

9564

result:

ok single line: '9564'

Test #5:

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

input:

16 18

output:

66116

result:

ok single line: '66116'

Test #6:

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

input:

18 10

output:

43140

result:

ok single line: '43140'

Test #7:

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

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: 5616kb

input:

2 49

output:

96

result:

ok single line: '96'

Test #9:

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

input:

7 38

output:

1598

result:

ok single line: '1598'

Test #10:

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

input:

19 6

output:

5524

result:

ok single line: '5524'

Test #11:

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

input:

31 49

output:

369127208

result:

ok single line: '369127208'

Test #12:

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

input:

44 30

output:

310756420

result:

ok single line: '310756420'

Test #13:

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

input:

49 2

output:

2

result:

ok single line: '2'

Test #14:

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

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: 7744kb

input:

2 319

output:

636

result:

ok single line: '636'

Test #16:

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

input:

89 44

output:

999831996

result:

ok single line: '999831996'

Test #17:

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

input:

280 279

output:

332244975

result:

ok single line: '332244975'

Test #18:

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

input:

282 500

output:

344135056

result:

ok single line: '344135056'

Test #19:

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

input:

464 211

output:

629248621

result:

ok single line: '629248621'

Test #20:

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

input:

499 500

output:

732883324

result:

ok single line: '732883324'

Test #21:

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

input:

500 2

output:

2

result:

ok single line: '2'

Test #22:

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

input:

500 324

output:

992004807

result:

ok single line: '992004807'

Subtask #4:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #23:

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

input:

2 4999

output:

9996

result:

ok single line: '9996'

Test #24:

score: 0
Accepted
time: 11ms
memory: 60248kb

input:

1988 4702

output:

182266147

result:

ok single line: '182266147'

Test #25:

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

input:

2500 5000

output:

765321947

result:

ok single line: '765321947'

Test #26:

score: 0
Accepted
time: 38ms
memory: 146524kb

input:

4388 4717

output:

253964546

result:

ok single line: '253964546'

Test #27:

score: 0
Accepted
time: 44ms
memory: 155032kb

input:

4611 4812

output:

467863120

result:

ok single line: '467863120'

Test #28:

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

input:

4825 2

output:

2

result:

ok single line: '2'

Test #29:

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

input:

5000 3

output:

10000

result:

ok single line: '10000'

Test #30:

score: 0
Accepted
time: 68ms
memory: 168568kb

input:

5000 5000

output:

325667260

result:

ok single line: '325667260'

Extra Test:

score: 0
Extra Test Passed