4.29 每日一题题解

小 C 的 01 序列

题目链接：https://cometoj.com/contest/84/problem/B?problem_id=4305

涉及知识点：

递推

solution：

(从1月29到今天，每日一题已经和大家陪伴了整整一个季度，继续加油吧，各位~)
(这道题的做法很多，简述个人的做法)
(先看一下前4项：)
(0)
(01)
(0110)
(01101001)
(发现每一项的前半部分等于上一项，后半部分等于前半部分取反)
(那递推式就很好写了：)
(00的个数 = 上一项00的个数+上一项11的个数)
(01的个数 = 上一项01的个数+上一项10的个数)
(10的个数 = 上一项10的个数+上一项01的个数)
(11的个数 = 上一项11的个数+上一项00的个数)
(写完发现还是少了点什么，举个例子，0110，我们只统计了01和10，漏掉了中间的11)
(所以少算的那一部分就是最中间新增的11)
(多写几项不难发现，当n为偶数，最中间的是11，n为奇数，最中间的是01)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
const int maxn = 1e5 + 5;
ll f[maxn][4];
int main(){
    int n;
    cin>>n;
    f[1][1] = 1;
    for(int i=2;i<=n;i++){
        f[i][0] = (f[i-1][0] + f[i-1][3])%mod;
        f[i][1] = (f[i-1][1] + f[i-1][2])%mod;
        f[i][2] = (f[i-1][2] + f[i-1][1])%mod;
        f[i][3] = (f[i-1][3] + f[i-1][0])%mod;
        if(i%2 == 0)
            f[i][3] += 1;
        else
            f[i][1] += 1;
    }
    for(int i=0;i<4;i++)
        cout<<f[n][i]<<" ";
    cout<<endl;
    return 0;
}