NOIP模拟58

本文主要是介绍NOIP模拟58，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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 }

矩阵乘法可应用与加速线性递推，中国剩余定理应用于当模数难以计算时分解为若干部分再将结果合并

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 }

这篇关于NOIP模拟58的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！