C - npcapc

liyixin0514 / 2024-10-23 / 原文

C - npcapc

题意

有 $t$ 次询问，每次给出一个 $n$，问有多少个长度为 $n$ 的包含大小写的字符串满足包含 $\texttt{NPCAPC}$ 和 $\texttt{npcapc}$ 两个子序列。$t\le 5000,n \le 10^9$。

思路

首先考虑直接计数，发现要去重，需要很复杂的容斥，很难做。

考虑 DP 然后矩阵快速幂优化。

设 $f_{i,x,y}$ 表示考虑到字符串第 $i$ 位，大写串已经匹配了 $x$ 位，小写串已经匹配了 $y$ 位，的方案数。枚举这一位填写什么字母即可转移。

考虑用矩阵快速幂优化 $i$ 这一维。把 $x,y$ 压成一维，初始矩阵是一个 $49\times 1$ 的矩阵，其中 $f_{0,0}=1$。转移矩阵是一个 $49 \times 49$ 的矩阵。因此求一个 $n$ 时间复杂度是 $m=49,O(m^3\log n)$ 的。

然而我们有 $t$ 次询问。$O(t m^3 \log n)$ 会爆。一个技巧是存下转移矩阵的 $2^0,2^1 ,\dots 2^k$ 次幂。因为矩阵乘法满足结合律，我们要求的是转移矩阵的若干次幂乘上初始矩阵，因此可以从右边往左边算，初始矩阵是 $m \times 1$ 的，这样时间复杂度就是 $O(m^2 \log n)$ 的了。预处理 $O(m^3 \log n)$，询问 $O(t m^2 \log n)$。

code

代码并不难写。自我感觉马蜂写得很优美很整洁。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int mod=998244353,B=49,lg=29;
int t,n;
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
void _add(int &a,int b) { a=add(a,b); }
struct juzhen {
	int x[B][B];
	juzhen () { memset(x,0,sizeof(x)); }
	juzhen operator * (const juzhen b) const {
		juzhen c;
		rep(i,0,B-1) rep(j,0,B-1) rep(k,0,B-1) _add(c.x[i][j],1ll*x[i][k]*b.x[k][j]%mod);
		return c;
	}
	void makezhuanyi() {
		x[0][0]=52;
		rep(i,1,6) x[i][i]=51;
		rep(i,1,6) x[i*7][i*7]=51;
		rep(i,1,6) rep(j,1,6) x[i*7+j][i*7+j]=50;
		rep(i,0,6) rep(j,1,6) x[i*7+j][i*7+j-1]=1;
		rep(i,1,6) rep(j,0,6) x[i*7+j][(i-1)*7+j]=1;
	}
}b[30],zhuanyi;
void init() {
	b[0]=zhuanyi;
	rep(i,1,lg) b[i]=b[i-1]*b[i-1];
}
struct juzhen2 {
	int x[B];
	juzhen2 () { memset(x,0,sizeof(x)); }
	void makeinit() { x[0]=1; }
}f0,ans;
juzhen2 operator * (juzhen a,juzhen2 b) {
	juzhen2 c;
	rep(i,0,B-1) rep(j,0,B-1) _add(c.x[i],1ll*a.x[i][j]*b.x[j]%mod);
	return c;
}
int main() {
	zhuanyi.makezhuanyi();
	sf("%d",&t);
	init();
	f0.makeinit();
	while(t--) {
		sf("%d",&n);
		ans=f0;
		rep(i,0,lg) {
			if((n>>i)&1) ans=b[i]*ans;
		}
		pf("%d\n",ans.x[48]);
	}
}