题解 | #c#

##C 含txt序列

代码是根据出题人写的题解写的 具体化实现了一下 弱鸡造福弱鸡

##思路

dp

**直接算出含txt的序列比较难，会一直有重复，所以转变思维，求不含txt的序列的个数，然后全排列减去它就是答案

f[i][j],表示以j结尾的不含txt串的序列的个数 ans=26^n-f[n][0]-f[n][1]-f[n][2] j=1表示以t结尾，j=2表示以tx结尾，j=0表示其他所有情况**

注意取模要每步取模 涉及到减法时要+mod取mod

##代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int f[200005][4] = { 0 };//f[i][j],表示以j结尾的不含txt串的序列的个数 ans=26^n-f[n][0]-f[n][1]-f[n][2] j=1表示以t结尾，j=2表示以tx结尾，j=0表示其他所有情况
int ks(int a) {
	int c = 26;
	int ans = 1;
	while (a) {
		if (a & 1) ans = (ans * c)%mod;
		c = (c * c) % mod;
		a >>= 1;
	}
	return ans;
}
signed main()
{
	f[0][0] = 1;
	for (int i = 1; i <= 200005; i++) {
		f[i][1] = (f[i - 1][1] + f[i - 1][0])%mod;
		f[i][2] = f[i - 1][1];
		f[i][0] = ((f[i - 1][1] * 24%mod + f[i - 1][2] * 25%mod )%mod+ f[i - 1][0] * 25%mod)%mod;
		           //t_ 排除尾部为t和为x的情况  tx_ 排除尾部为t的情况 不可能为tx    __排除尾部为t的情况 不可能为tx
	}
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << (ks(n)- ((f[n][1] + f[n][0])%mod + f[n][2])%mod+mod)%mod<<endl;//一直取mod 结果会有负数得加mod余mod
	}
	return 0;
}