题意 :
实际上可以转化一下题意
要求求出用三个不同元素的字符集例如 { 'A' 、'B' 、'C' }
构造出长度为 n 且不包含
AAA、BBB
CCC、ACB
BCA、CAC
CBC
这其中任意一个字符串的方案数
分析 :
方法一 （BM 求线性递推）
直接暴力出前 10 项的答案、然后猜它其实可以由线性递推递推而来
丢进杜教的 BM 模板里面就可以直接求出第 N 项了
实际上这个可以不用猜、这种不包含某些串的题目
如果你做过类似的、就会知道实际上是可以构造出一个矩阵然后快速幂
可以使用矩阵快速幂优化的递推方程大概都可以用 BM 求
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
;
ll powmod(ll a,ll b) {ll res=;a%=mod; assert(b>=); ){)res=res*a%mod;a=a*a%mod;}return res;}
// head
ll n;
namespace linear_seq {
;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
rep(i,,k+k) _c[i]=;
rep(i,,k) ,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
;i>=k;i--) if (_c[i])
rep(j,,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
ll ans=,pnt=;
int k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,,k) _md[k--i]=-a[i];_md[k]=;
Md.clear();
rep(i,,k) ) Md.push_back(i);
rep(i,,k) res[i]=;
res[]=;
while ((1ll<<pnt)<=n) pnt++;
;p--) {
mul(res,res,k);
) {
;i>=;i--) res[i+]=res[i];res[]=;
rep(j,,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,,k) ans=(ans+res[i]*b[i])%mod;
) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(,),B(,);
,m=,b=;
rep(n,,SZ(s)) {
ll d=;
rep(i,,L+) d=(d+(ll)C[i]*s[n-i])%mod;
) ++m;
*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-)%mod;
);
rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+-L; B=T; b=d; m=;
} else {
ll c=mod-d*powmod(b,mod-)%mod;
);
rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};
int main() {
vector<int>v;
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
int nCase;
scanf("%d", &nCase);
while(nCase--){
scanf("%lld", &n);
printf() % mod);
}
}
方法二 （AC自动机构造矩阵 + 矩阵快速幂）
如果你做过 POJ 2778 那么你就能够知道这个题目
实际上将不合法的字符串丢到 AC 自动机里面去就可以构造出矩阵了
然后进行快乐的矩阵快速幂就阔以了
下面代码并非 AC 代码、只是使用 AC 自动机构造矩阵的代码
且代码大部分都使用了我写过的 POJ 2778 的代码、输入形式可看代码最后注释
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
;
;
;
int maxn;
];
][]; }unit, M;
mat operator * (mat a, mat b)
{
mat ret;
long long x;
; i<maxn; i++){
; j<maxn; j++){
x = ;
; k<maxn; k++){
x = (x + ((long long)a.m[i][k]%MOD * b.m[k][j]%MOD)%MOD)%MOD;
}
ret.m[i][j] = x % MOD;
}
}
return ret;
}
inline ; i<maxn; i++) unit.m[i][i] = ; }
mat pow_mat(mat a, int n)
{
mat ret = unit;
while(n){
) ret = ret * a;
a = a*a;
n >>= ;
}
return ret;
}
struct Aho{
struct StateTable{
int Next[Letter];
int fail, flag;
}Node[Max_Tot];
int Size;
queue<int> que;
inline void init(){
while(!que.empty()) que.pop();
memset(Node[].Next, , ].Next));
Node[].fail = Node[].flag = ;
Size = ;
}
inline void insert(char *s){
;
; s[i]; i++){
int idx = mp[s[i]];
if(!Node[now].Next[idx]){
memset(Node[Size].Next, , sizeof(Node[Size].Next));
Node[Size].fail = Node[Size].flag = ;
Node[now].Next[idx] = Size++;
}
now = Node[now].Next[idx];
}
Node[now].flag = ;
}
inline void BuildFail(){
Node[].fail = ;
que.push();
while(!que.empty()){
int top = que.front(); que.pop();
;///如果当前节点的Fail指针指向的节点也是末尾节点，那么这个节点也是不合法的！
; i<Letter; i++){
if(Node[top].Next[i]){
) Node[ Node[top].Next[i] ].fail = ;
else{
int v = Node[top].fail;
){
if(Node[v].Next[i]){
Node[ Node[top].Next[i] ].fail = Node[v].Next[i];
break;
}v = Node[v].fail;
}) Node[ Node[top].Next[i] ].fail = ;
}que.push(Node[top].Next[i]);
}?Node[ Node[top].fail ].Next[i]:;///多了这一句！
}
}
}
inline void BuildMatrix(){
; i<Size; i++)
; j<Size; j++)
M.m[i][j] = ;
; i<Size; i++){
; j<Letter; j++){
if(!Node[i].flag && !Node[ Node[i].Next[j] ].flag)
M.m[i][Node[i].Next[j]]++;
}
}
maxn = Size;
}
}ac;
];
int main(void)
{
mp[,
mp[,
mp[;
int n, m;
while(~scanf("%d %d", &m, &n)){
ac.init();
; i<m; i++){
scanf("%s", S);
ac.insert(S);
}
ac.BuildFail();
ac.BuildMatrix();
; i<; i++){
; j<; j++){
printf("%d ", M.m[i][j]);
}puts("");
}puts("");
init_unit();
M = pow_mat(M, n);
// for(int i=0; i<10; i++){
// for(int j=0; j<10; j++){
// printf("%d ", M.m[i][j]);
// }puts("");
// }puts("");
;
; i<ac.Size; i++)
ans = (ans + M.m[][i])%MOD;
ans %= MOD;
printf("%d\n", ans);
}
;
}
/*输入 7 和 n 然后输入字符集、就能出答案*/
/**
7 15
AAA
BBB
CCC
ACB
BCA
CAC
CBC
*/
方法三 （手动构造矩阵 + 矩阵快速幂）
首先使用各种手段抓一个聪明伶俐的队友过来
此队友需要在矩阵构造方面颇有灵性
把题目交给他翻译、构思、打代码
等待 15 分钟左右、最后即可得到 Accept