『SNKOI』R2 | T2 题解

JHR100330 · 2025-06-06 16:25:07 · 题解

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

首先翻译一下题目，即序列第 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

#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;
}