T2：
首先对于非常规模数要思考其是否为质数，因为逆元与费马小定理建立在质数（互质）情况下
那么对于模数非质数的问题，通常的解决方法为唯一分解，即将模数分解为若干质数之积，再通过
中国剩余定理合并
对于本题，发现模数为5个连续质数之积，又给出了公式二，因此基本思路非常简单，利用基本公式二
作矩阵乘法优化递推，对每个模数计算出x，最终将x模原质数即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define fir first
14 #define sec second
15 #define lowbit(x) (x & -x)
16 const I N = 56569200, mod = 95041567;
17 I T,gcd,A[47],F[47][47],G[6];
18 I prime[6] = {0,31,37,41,43,47};
19 I Bel[47];
20 vector <I> _C[48];
21 inline I read () {
22 I x(0),y(1); C z(getchar());
23 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
24 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
25 return x * y;
26 }
27 inline V Max (I &a,I b) { a = a > b ? a : b; }
28 inline V Min (I &a,I b) { a = a < b ? a : b; }
29 inline I max (I a,I b) { return a > b ? a : b; }
30 inline I min (I a,I b) { return a < b ? a : b; }
31 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
32 inline I fp (I a,I b) { I ans(1);
33 for (; b ;b >>= 1, a = 1ll * a * a % mod)
34 if (b & 1) ans = 1ll * ans * a % mod;
35 return ans;
36 }
37 I Exgcd (I a,I b,I &x,I &y) {
38 if (b == 0) {
39 x = 1, y = 0;
40 return a;
41 }
42 gcd = Exgcd (b,a % b,x,y);
43 I tmp (x);
44 x = y;
45 y = tmp - a / b * y;
46 return gcd;
47 }
48 I China () {
49 I x,y,a(0),m;
50 for (I i(1);i <= 5; ++ i) {
51 m = mod / prime[i];
52 Exgcd (prime[i],m,x,y);
53 a = (a + 1ll * y * m * G[i] % mod) % mod;
54 }
55 if (a > 0) return a;
56 else return a + mod;
57 }
58 inline V Make (I size) {
59 for (I i(0);i < size; ++ i)
60 A[i] = Bel[i + 1] % size;
61 for (I j(0);j < size; ++ j)
62 for (I i(0);i < size; ++ i)
63 F[i][j] = j == i - 1;
64 F[0][size - 1] = F[1][size - 1] = 1;
65 }
66 inline V Matrix_mul (I size) {
67 I X[47];
68 memset (X,0,sizeof X);
69 for (I k(0);k < size; ++ k)
70 for (I j(0);j < size; ++ j)
71 (X[j] += 1ll * A[k] * F[k][j] % mod) %= mod;
72 memcpy (A,X,sizeof X);
73 }
74 inline V Matrix_self (I size) {
75 I X[47][47];
76 memset (X,0,sizeof X);
77 for (I i(0);i < size; ++ i)
78 for (I k(0);k < size; ++ k)
79 for (I j(0);j < size; ++ j)
80 (X[i][j] += 1ll * F[i][k] * F[k][j] % mod) %= mod;
81 memcpy (F,X,sizeof X);
82 }
83 inline V FMP (I t,I size) {
84 for (; t ;t >>= 1, Matrix_self (size))
85 if (t & 1) Matrix_mul (size);
86 }
87 inline V Figure (I t) {
88 for (I i(1);i <= 5; ++ i) {
89 Make (prime[i]);
90 if (t > prime[i]) {
91 FMP (t - prime[i],prime[i]);
92 G[i] = A[prime[i] - 1];
93 }
94 else
95 G[i] = A[t - 1];
96 }
97 printf ("%lld\n",China () % mod);
98 }
99 signed main () {
100 T = read();
101 _C[0].push_back (1), _C[0].push_back (0);
102 for (I i(1);i < 48; ++ i) {
103 _C[i].push_back (1);
104 for (I j(1);j <= i; ++ j)
105 _C[i].push_back ((_C[i - 1][j - 1] + _C[i - 1][j]) % mod);
106 _C[i].push_back (0);
107 }
108 Bel[0] = 1;
109 for (I i(1);i < 48; ++ i)
110 for (I j(0);j < i; ++ j)
111 (Bel[i] += 1ll * _C[i - 1][j] * Bel[j] % mod) %= mod;
112 while (T -- )
113 Figure (read());
114 }
View Code
矩阵乘法可应用与加速线性递推，中国剩余定理应用于当模数难以计算时分解为若*分再将结果合并
T3：
正解AC自动机+DP，考虑首先模型是对的，多字符串匹配，只不过有限制转移，考场考虑成计数问题
于是就挂了，考虑设Fijkl表示当前字符串长度为i，有j个R，已经转移到AC自动机上k节点，l为0，1，2，3
表示是否包含两个字符串，最终目标为F(n+m)(m)()(3)
AC自动机+DP关键在于AC自动机的失配指针，利用其直接转移到下一个合法位置，另一在于AC自动机建立过程中
失配指针的建立过程，需要注意利用fail指针的传递将信息进行传递，即若某些问题中子串与母串具有相同性质，需要
传递信息
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define fir first
14 #define sec second
15 #define lowbit(x) (x & -x)
16 const I M = 105, mod = 1e9 + 7;
17 I f[M << 1][M][M << 1][4];
18 C s[M];
19 inline I read () {
20 I x(0),y(1); C z(getchar());
21 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
22 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
23 return x * y;
24 }
25 inline V Max (I &a,I b) { a = a > b ? a : b; }
26 inline V Min (I &a,I b) { a = a < b ? a : b; }
27 inline I max (I a,I b) { return a > b ? a : b; }
28 inline I min (I a,I b) { return a < b ? a : b; }
29 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
30 struct AC {
31 #define c (s[i] == 'R')
32 I tot,it[M << 1][2],fail[M << 1],End[M << 1];
33 inline V insert (I idx) {
34 I pos(0);
35 for (I i(0); s[i] ; ++ i) {
36 if (!it[pos][c])
37 it[pos][c] = ++tot;
38 pos = it[pos][c];
39 }
40 End[pos] |= idx;
41 }
42 inline V found () {
43 queue <I> q;
44 if (it[0][0]) q.push (it[0][0]);
45 if (it[0][1]) q.push (it[0][1]);
46 while (!q.empty ()) {
47 I x (q.front ()); q.pop ();
48 if (it[x][1]) fail[it[x][1]] = it[fail[x]][1], q.push (it[x][1]);
49 else it[x][1] = it[fail[x]][1];
50 if (it[x][0]) fail[it[x][0]] = it[fail[x]][0], q.push (it[x][0]);
51 else it[x][0] = it[fail[x]][0];
52 End[it[x][1]] |= End[it[fail[x]][1]];
53 End[it[x][0]] |= End[it[fail[x]][0]];
54 }
55 }
56 inline V clear () {
57 for (I i(0);i <= tot; ++ i)
58 it[i][0] = it[i][1] = fail[i] = End[i] = 0;
59 tot = 0;
60 }
61 }AC;
62 signed main () {
63 I T(read());
64 while (T -- ) {
65 AC.clear ();
66 I ans(0), m(read()), n(read());
67 scanf ("%s",s); AC.insert (1);
68 scanf ("%s",s); AC.insert (2);
69 AC.found ();
70 f[0][0][0][0] = 1;
71 for (I i(0);i <= n + m; ++ i)
72 for (I j(0);j <= i; ++ j) {
73 if (j > m || i - j > n) continue;
74 for (I k(0);k <= AC.tot; ++ k) {
75 for (I l(0);l <= 3; ++ l) {
76 (f[i + 1][j + 1][AC.it[k][1]][l | AC.End[AC.it[k][1]]] += f[i][j][k][l]) %= mod;
77 (f[i + 1][ j ][AC.it[k][0]][l | AC.End[AC.it[k][0]]] += f[i][j][k][l]) %= mod;
78 }
79 }
80 }
81 for (I i(0);i <= AC.tot; ++ i)
82 (ans += f[n + m][m][i][3]) %= mod;
83 printf ("%d\n",ans);
84 for (I i(0);i <= n + m + 1; ++ i)
85 for (I j(0);j <= i + 1; ++ j)
86 for (I k(0);k <= AC.tot; ++ k)
87 f[i][j][k][0] = f[i][j][k][1] = f[i][j][k][2] = f[i][j][k][3] = 0;
88 }
89 }
View Code