『SNKOI』R2 | T2 题解

依旧卡常。空间不够，不能开数组，用滚动变量优化。

首先翻译一下题目，即序列第

0

位为

n

，若

i \ge a_{i - 1} (1 \le i \le n)

，则

A_i = A_{i - 1} - i

，否则

A_i = A_{i - 1} + i

。

由于

a_i

仅与

a_{i - 1}

和

i

有关，用一个变量滚动，再用

sum

统计总和即可。

时间复杂度

O(n)

Code

CPP

#include<cstdio>

#define ll long long

const int MOD = 998244353;
int n, m;
ll sum; 

int main(){
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
    scanf("%d", &n); m = n, sum = n;
    for(int i = 1; i <= n; i ++){
		if(m >= i) m = m - i;
		else m = m + i;
		sum = (sum + m) - (sum + m >= MOD) * MOD;
	}
	printf("%lld\n", sum);
    return 0;
}

『SNKOI』R2 | T2 题解

文章操作

Code

相关推荐

评论

『SNKOI』R2 | T2 题解