#include<stdio.h>
#define x 998244353
long long f2(int n);
long long f3(int n);
long long f1(int n){
    if(n==1) return 1;
    else if(n==2) return 2;
    return f3(n-1)%x+f2(n-1)/2%x;
}
long long f2(int n){
    if(n==1) return 1;
    else if(n==2) return 2;
    return f1(n-1)%x+f3(n-1)%x;
}
long long f3(int n){
    if(n==1) return 1;
    else if(n==2) return 2;
    return f1(n-1)%x+f2(n-1)/2%x;
}
int main(){
    int n;
    scanf("%d",&n);
    long long ans=(f1(n)+f2(n)+f3(n))%x;
    printf("%lld",ans);
    return 0;
}
Geopelia 正在打音游。
现在按键序列可以看做一个长度为n的序列[a1,a2,⋯,an]。
特别地，这个序列满足每一项ai都是1,2,3中的一个，且相邻的两项 ai≠ai+1
Geopelia 认为一个序列是不卡手的，当且仅当序列中没有出现连续的子串 [1,2,3]或 [3,2,1]
问一共有多少个不同的不卡手的序列，且长度为 n？
由于答案很大，你应当输出答案除以 998244353的余数。
输入
一个整数 n
保证 3≤n≤2×105
输出
答案对 998244353取模的余数。
输入样例 1
3
输出样例 1
10
输入样例 2
4
输出样例 2
16
输入样例 3
100
输出样例 3
485170147

什么鬼？可以猜出应该是：相邻的两项 aᵢ≠aᵢ₊₁

这就矛盾了！序列本身就是有序的，应该说成“当且仅当序列中没有出现子串[1,2,3]或[3,2,1]”，“连续的子串[1,2,3]”应该指的是[1,2,3,1,2,3]

你的代码计算 f(100) 时，需要用到 f(10)；计算f(99) 时，需要用到 f(10)；计算f(98) 时，需要用到 f(10)，……。那么f(10)就被重复计算了一次又一次，呈指数级增长。
要么，弄个 cache，把已经计算完毕的保存下来，避免以后重复计算；要么，反过来，从地往高运算。

f2(n-1)本身是%x得来的， a%x / 2 % x 可不等于 a/2 % x。
打个比方，假如模除之前的 f2 原始值为 12，x为10，那么 f2/2 == 6，而 f2%x/2 == 1


改掉以上错误后，代码如下（没法验证，不保证正确）

#include <stdio.h>

unsigned foo( unsigned n )
{
    if( n < 3 )
        return 3*n;

    // 4个 小于998244353的数 相加，结果小于2^32-1，所以使用 uint32_t 即可
    const unsigned x = 998244353;
    unsigned f1=2, f2=2, f3=2;
    for( unsigned i=2; i!=n; ++i )
    {
        unsigned f1_new = (f2/2 + f3)%x;
        unsigned f2_new = (f1 + f3)%(2*x);
        unsigned f3_new = (f2/2 + f1)%x;
        f1 = f1_new;
        f2 = f2_new;
        f3 = f3_new;
    }
    return (f1+f2+f3)%x;
}

//#include <assert.h>

int main( void )
{
    //assert( foo(1)==3 );
    //assert( foo(2)==6 );
    //assert( foo(3)==10 );
    //assert( foo(4)==16 );
    //assert( foo(100)==485170147 );

    unsigned n;
    scanf( "%u", &n );
    printf( "%u", foo(n) );
}

我艹 恐怖如斯

证明 a/2 % x 不等于 a%x / 2
反证法：设 a=12, x=10，则 左式等于6，右式等于 1

证明 a/2 % x 等于 a%(2*x) / 2
设 a = n*(2*x) + k，其中 k<2*x，则
左式 = (n*(2*x) + k)/2 % x = (n*x+k/2)%x = k/2
右式 = (n*(2*x) + k)%(2*x) / 2 = k/2
得证