#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; const int N = 55;
ll n, M;
int len, f[N];
char s[N]; void getFail() { int j = 0; for(int i=1;i<=len-1;i++){ while (j&&s[j]!=s[i]) j=f[j]; if (s[j]==s[i]) ++j; f[i+1] = j; }
} ull qmul(const ull a, const ull b, const ull md) {
ll c=(ll)a*b-(ll)((ull)((long double)a*b/md)*md);
return c<0?md+c:((ull)c>md?c-md:c);
} struct Mat { ll v[55][55]; Mat() {memset(v, 0, sizeof v);} Mat operator * (const Mat& b) const { Mat c; for(int k=0;k<=len;k++) for(int i=0;i<=len;i++) for(int j=0;j<=len;j++){ c.v[i][j] = (qmul(v[i][k],b.v[k][j],M)+c.v[i][j])%M; } return c; } Mat operator ^ (ll nn) { Mat b, a=*this; for(int i=0;i<=len;i++) b.v[i][i]=1; while(nn) { if(nn&1LL) b=b*a; nn>>=1LL,a=a*a; } return b; }
}; int main() { int t; scanf("%d", &t); while (t--) { scanf("%lld%lld%s", &n, &M, s); len = strlen(s); getFail(); Mat g; for(int i=0;i<=len;i++) for(int k='a';k<='z';k++) { int nxt = i; while (nxt&&s[nxt]!=k) nxt = f[nxt]; if (s[nxt]==k) ++nxt; if (i==len) nxt = len; ++g.v[nxt][i]; } g = g^n; printf("%lld\n", g.v[len][0]); }
}
uj5u.com熱心網友回復：
排列組合與統計注意重復，例如ab 長度為4. abab注意不要算兩次。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61550.html
標籤：C++ 語言