题解：P16681 玩具

· · 题解

前一天熬夜所以状态烂完了，10min 左右搞完 A 结果半天没想出来 B，怕掉分就没打 /fad

我好困啊呜呜呜。该去睡午觉的，结果跑去看番了，等会 abc 也趋势了就好笑了。

考虑链怎么处理。

这个可以直接 dp，设计状态 f_{0/1,i} 表示处理到第 i 位且最后一位是否是元音的方案数。

答案的三个链方案相同，能否拼接取决于首尾的种类。

于是我们单独对每个情况处理 dp 就好。

合并列的答案，逐列再 dp 一遍就好了。

实现可以看代码。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int dp[400005][2][2];
int dp2[10][2][2];
signed main(){
    int n=341799;
    dp[1][1][1]=5;
    dp[1][0][0]=21;
    for(int i=2;i<=n;i++){
        dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][0][1])*21%mod;
        dp[i][0][1]=dp[i-1][0][0]*5%mod;
        dp[i][1][0]=(dp[i-1][1][0]+dp[i-1][1][1])*21%mod;
        dp[i][1][1]=dp[i-1][1][0]*5%mod;
    }
    dp2[1][0][0]=dp[n][0][0];
    dp2[1][0][1]=dp[n][0][1];
    dp2[1][1][0]=dp[n][1][0];
    dp2[1][1][1]=dp[n][1][1];
    dp2[2][0][0]=(dp2[1][0][0]+dp2[1][0][1]+dp2[1][1][0]+dp2[1][1][1])*21%mod*21%mod;
    dp2[2][0][1]=(dp2[1][0][0]+dp2[1][1][0])*21%mod*5%mod;
    dp2[2][1][0]=(dp2[1][0][0]+dp2[1][0][1])*5%mod*21%mod;
    dp2[2][1][1]=(dp2[1][0][0])*5%mod*5%mod;
    dp2[3][0][0]=(dp2[2][0][0]+dp2[2][0][1]+dp2[2][1][0]+dp2[2][1][1])*dp[n][0][0]%mod;
    dp2[3][0][1]=(dp2[2][0][0]+dp2[2][1][0])*dp[n][0][1]%mod;
    dp2[3][1][0]=(dp2[2][0][0]+dp2[2][0][1])*dp[n][1][0]%mod;
    dp2[3][1][1]=(dp2[2][0][0])*dp[n][1][1]%mod;
    dp2[4][0][0]=(dp2[3][0][0]+dp2[3][0][1]+dp2[3][1][0]+dp2[3][1][1])*21%mod*21%mod;
    dp2[4][0][1]=(dp2[3][0][0]+dp2[3][1][0])*21%mod*5%mod;
    dp2[4][1][0]=(dp2[3][0][0]+dp2[3][0][1])*5%mod*21%mod;
    dp2[4][1][1]=(dp2[3][0][0])*5%mod*5%mod;
    dp2[5][0][0]=(dp2[4][0][0]+dp2[4][0][1]+dp2[4][1][0]+dp2[4][1][1])*dp[n][0][0]%mod;
    dp2[5][0][1]=(dp2[4][0][0]+dp2[4][1][0])*dp[n][0][1]%mod;
    dp2[5][1][0]=(dp2[4][0][0]+dp2[4][0][1])*dp[n][1][0]%mod;
    dp2[5][1][1]=(dp2[4][0][0])*dp[n][1][1]%mod;
    cout<<(dp2[5][0][0]+dp2[5][0][1]+dp2[5][1][0]+dp2[5][1][1])%mod;
    return 0;
}
//『要是威廉先生知道的话，一定会骂我的吧。』

//『要是纳莎妮亚知道的话，绝对会很傻眼吧。』

// 嘻嘻嘻地笑著。啊哈哈地笑著。她……她们是坏孩子。让那么为她们著想的人死去，不仅如此，现在也在违抗他们的意志，不停重复做一些让他们感到生气、傻眼的事。

//『虽然我没有资格获得幸福……』

//『但是……』

// 就算如此，也一定是……