UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206554#3708. routecql100503ms2124kbC++111.1kb2024-07-23 18:11:492024-07-23 20:07:12

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

string add(string a, string b) {
	string res(max(a.size(), b.size()) + 1, 0);
	res[0] = '0';
	for (int i = 1; i < res.size(); i++) {
		res[res.size() - i] += ((i <= a.size() ? a[a.size() - i] - '0' : 0) + (i <= b.size() ? b[b.size() - i] - '0' : 0));
		res[res.size() - i - 1] += res[res.size() - i] / 10;
		res[res.size() - i] = res[res.size() - i] % 10 + '0';
	}
	return res.substr(res[0] == '0');
}

signed main() {
	vector<vector<string>> v(3, vector<string>(1005, "0")), v2(3, vector<string>(1005, "0"));
	v[1][1] = "1";
	for (int j = 1; j <= 1001; j++) {
		v[1][j] = add(v[1][j], add(v[1][j - 1], v[2][j - 1]));
		v[2][j] = add(v[2][j], add(v[1][j], v[2][j - 1]));
	}
	v2[2][1] = "1";
	for (int j = 2; j <= 1001; j++) {
		v2[1][j] = add(v2[1][j], add(v2[1][j - 1], v2[2][j - 1]));
		v2[2][j] = add(v2[2][j], add(v2[1][j], v2[2][j - 1]));
	}
	int a, b, x;
	cin >> a >> b;
	x = b - a + (a + 1) % 2 + 1;
	if (a % 2)
		cout << v[(x + 1) % 2 + 1][(x + 1) / 2] << endl;
	else
		cout << v2[(x + 1) % 2 + 1][(x + 1) / 2] << endl;
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 25ms
memory: 2120kb

input:

943 949

output:

13

result:

ok single line: '13'

Test #2:

score: 5
Accepted
time: 25ms
memory: 2120kb

input:

175 189

output:

610

result:

ok single line: '610'

Test #3:

score: 5
Accepted
time: 28ms
memory: 2120kb

input:

445 467

output:

28657

result:

ok single line: '28657'

Test #4:

score: 5
Accepted
time: 24ms
memory: 2120kb

input:

598 610

output:

233

result:

ok single line: '233'

Test #5:

score: 5
Accepted
time: 29ms
memory: 2120kb

input:

409 437

output:

514229

result:

ok single line: '514229'

Test #6:

score: 5
Accepted
time: 27ms
memory: 2124kb

input:

47 55

output:

34

result:

ok single line: '34'

Test #7:

score: 5
Accepted
time: 27ms
memory: 2124kb

input:

835 868

output:

5702887

result:

ok single line: '5702887'

Test #8:

score: 5
Accepted
time: 28ms
memory: 2124kb

input:

589 638

output:

12586269025

result:

ok single line: '12586269025'

Test #9:

score: 5
Accepted
time: 27ms
memory: 2120kb

input:

837 969

output:

2791715456571051233611642553

result:

ok single line: '2791715456571051233611642553'

Test #10:

score: 5
Accepted
time: 28ms
memory: 2124kb

input:

145 248

output:

2427893228399975082453

result:

ok single line: '2427893228399975082453'

Test #11:

score: 5
Accepted
time: 28ms
memory: 2124kb

input:

461 619

output:

757791618667731139247631372100066

result:

ok single line: '757791618667731139247631372100066'

Test #12:

score: 5
Accepted
time: 21ms
memory: 2120kb

input:

590 779

output:

2281217241465037496128651402858212007295

result:

ok single line: '2281217241465037496128651402858212007295'

Test #13:

score: 5
Accepted
time: 28ms
memory: 2124kb

input:

307 459

output:

42230279526998466217810220532898

result:

ok single line: '42230279526998466217810220532898'

Test #14:

score: 5
Accepted
time: 28ms
memory: 2120kb

input:

768 888

output:

8670007398507948658051921

result:

ok single line: '8670007398507948658051921'

Test #15:

score: 5
Accepted
time: 24ms
memory: 2120kb

input:

5 999

output:

3919377061614427623668052985592742430389065042819420493170692719480242247392252775480208752179017313...

result:

ok single line: '391937706161442762366805298559...9865808814650408864891823186505'

Test #16:

score: 5
Accepted
time: 24ms
memory: 2124kb

input:

4 999

output:

6341685300418834712936873743652479702279493077782703784593930186219165735154458712792650716708440646...

result:

ok single line: '634168530041883471293687374365...5783715452104982240098275933872'

Test #17:

score: 5
Accepted
time: 16ms
memory: 2120kb

input:

1 997

output:

1026106236203326233660492672924522213266855812060212427776462290569940798254671148827285946888745795...

result:

ok single line: '102610623620332623366049267292...5649524266755391104990099120377'

Test #18:

score: 5
Accepted
time: 21ms
memory: 2120kb

input:

1 998

output:

1660274766245209704954180047289770183494805119838482806235855309191857371770117020106551018559589860...

result:

ok single line: '166027476624520970495418004728...1433239718860373345088375054249'

Test #19:

score: 5
Accepted
time: 25ms
memory: 2124kb

input:

1 999

output:

2686381002448535938614672720214292396761660931898695234012317599761798170024788168933836965448335656...

result:

ok single line: '268638100244853593861467272021...7082763985615764450078474174626'

Test #20:

score: 5
Accepted
time: 20ms
memory: 2120kb

input:

1 1000

output:

4346655768693745643568852767504062580256466051737178040248172908953655541794905189040387984007925516...

result:

ok single line: '434665576869374564356885276750...8516003704476137795166849228875'