A – 等差子序列
因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。
因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。
哇这道题还是很神仙的。
首先,有递推式:
\[ f_i = \left(\prod_{j = 1}^{k} f_{i – j}^{b_j}\right) \bmod p \]
题目会给出一个\(f_n=m\),且这个数列前面的项都是\(1\),可看作次数为\(0\)的常数项。我们会发现,对于\(f_j,j>k\),都可以写成\(f_k^{C}\),其中\(C\)是一个多项式。这个多项式可以通过线性递推得到:
\[ C_i = (\sum_{j = 1}^{k} b_jC_{i-j}) \mod (p-1) \]
看到数据范围,考虑用矩阵乘法在\(O(n^3 \log n)\)的时间内得到\(C_n\)。所以现在我们有:
\[ f_k^{C_k} \equiv m \;(mod \; p) \]
我们现在已知\(k,m,p,C_n\),我们现在要求\(f_k\)。考虑使用原根来搞。众所周知,998244353 的原根是 3。原根的幂可以填充整个模\(p\)剩余系,所以可以考虑把这个式子写成:
\[ (3^t)^{C_k} \equiv 3^s \;(mod \; p), \text{其中设}m = 3^s, f_k = 3^t \]
我们把离散对数搞下来,变成:
\[ t*C_k \equiv s \; (mod \; p-1) \]
这个用 BSGS 搞下就可以得出结果\(s\)。然后用 exgcd 算出同余方程的解(顺便判别有无解)。算出\(t\)之后快速幂一下输出。
// CF1106F.cpp #include <bits/stdc++.h> #define ll long long using namespace std; // TODO: Make it fit to the matrix power; const int MAX_MAT = 150, mod = 998244353; int n, m, k, ki[MAX_MAT]; struct matrix { ll mat[MAX_MAT][MAX_MAT]; void basify() { for (int i = 1; i <= k; i++) mat[i][i] = 1; } ll *operator[](const int &id) { return mat[id]; } matrix operator*(const matrix &mt) const { matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); for (int i = 1; i <= k; i++) for (int j = 1; j <= k; j++) for (int mid = 1; mid <= k; mid++) ans.mat[i][j] = (ans.mat[i][j] + mat[i][mid] * mt.mat[mid][j] % (mod - 1)) % (mod - 1); return ans; } matrix operator^(const int &tim) const { matrix ans, bas = *this; ans.basify(); int ti = tim; while (ti) { if (ti & 1) ans = ans * bas; bas = bas * bas; ti >>= 1; } return ans; } }; ll quick_pow(ll bas, ll tim) { ll ans = 1; while (tim) { if (tim & 1) ans = ans * bas % mod; bas = bas * bas % mod; tim >>= 1; } return ans; } ll bsgs(ll a, ll y) { if (a == 0 && y == 0) return 1; if (a == 0 && y != 0) return -1; map<ll, ll> hsh; ll u = ceil(sqrt(mod)); for (int i = 0, x = 1; i <= u; i++, x = x * a % mod) hsh[y * x % mod] = i; ll unit = quick_pow(a, u); for (int i = 1, x = unit; i <= u; i++, x = x * unit % mod) if (hsh.count(x)) return i * u - hsh[x]; return -1; } ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, x, y), z = x; x = y, y = z - (a / b) * y; return d; } ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); } ll solve(ll a, ll b, ll c) { if (b == 0) return 0; ll d = gcd(a, b); a /= d, b /= d; if (gcd(a, c) != 1) return -1; ll res, tmp; exgcd(a, c, res, tmp); res = res * b % c; res = (res + c) % c; return res; } int main() { scanf("%d", &k); for (int i = 1; i <= k; i++) scanf("%d", &ki[i]); scanf("%d%d", &n, &m); matrix B; for (int i = 1; i <= k; i++) B[1][i] = ki[i]; for (int i = 2; i <= k; i++) B[i][i - 1] = 1; B = B ^ (n - k); ll res = B[1][1], s = bsgs(3, m), ans = solve(res, s, mod - 1); if (ans == -1) puts("-1"); else printf("%lld", quick_pow(3, ans)); return 0; }
对,这道题是毒瘤题。首先,我们可以判定出,这些序列一定会在\(60s\)内全部从头开始,因为\(1,2,3,4,5,6\)的最大公倍数为\(60\)。之后,我们可以考虑把这些操作放入操作矩阵之中。操作矩阵的长宽都为\(n*m\)。具体的操作对应如下:
然后算出\(p=\lfloor \frac{m}{60} \rfloor, q = m \mod 60\),进行矩阵快速幂和连续乘法即可。
好毒瘤,建议不要写。
// CH3401.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 70; ll N, M, t, act; char opt[MAX_N][MAX_N]; string opts[MAX_N]; struct matrix { ll mat[MAX_N][MAX_N], n, m; matrix() { memset(mat, 0, sizeof(mat)); } matrix(int n, int m) { this->n = n, this->m = m; for (int i = 1; i <= max(n, m); i++) mat[i][i] = 1; } matrix operator*(const matrix &tar) const { matrix ans = matrix(); ans.n = n, ans.m = tar.m; for (int i = 0; i <= n; i++) for (int j = 0; j <= tar.m; j++) for (int k = 0; k <= m; k++) ans.mat[i][j] += mat[i][k] * tar.mat[k][j]; return ans; } matrix operator^(const int &tim) const { int ti = tim; matrix ans, bas = *this; for (int i = 0; i <= max(n, m); i++) ans.mat[i][i] = 1; ans.n = n, ans.m = m; while (ti) { if (ti & 1) ans = ans * bas; bas = bas * bas; ti >>= 1; } return ans; } } P, Q, mats[70]; ll getPos(ll x, ll y) { return (x - 1) * M + y; } int main() { scanf("%lld%lld%lld%lld", &N, &M, &t, &act); for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> opt[i][j], opt[i][j] -= '0'; for (int i = 0; i < act; i++) cin >> opts[i]; int p = t / 60, q = t % 60; matrix F; F.n = 0, F.m = getPos(N, M), F.mat[0][0] = 1; for (int tim = 1; tim <= 60; tim++) { matrix current; current.n = getPos(N, M), current.m = getPos(N, M); current.mat[0][0] = 1; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { int pos = (tim - 1) % (opts[opt[i][j]].size()); char op = opts[opt[i][j]][pos]; switch (op) { case 'N': if (i > 1) current.mat[getPos(i, j)][getPos(i - 1, j)] = 1; break; case 'S': if (i < N) current.mat[getPos(i, j)][getPos(i + 1, j)] = 1; break; case 'E': if (j < M) current.mat[getPos(i, j)][getPos(i, j + 1)] = 1; break; case 'W': if (j > 1) current.mat[getPos(i, j)][getPos(i, j - 1)] = 1; break; case 'D': break; default: current.mat[0][getPos(i, j)] = op - '0'; current.mat[getPos(i, j)][getPos(i, j)] = 1; break; } } mats[tim] = current; } P = mats[1]; for (int i = 2; i <= 60; i++) P = P * mats[i]; P = P ^ p; Q = q == 0 ? matrix(getPos(N, M), getPos(N, M)) : mats[1]; for (int i = 2; i <= q; i++) Q = Q * mats[i]; F = F * P * Q; ll ans = 0; for (int i = 1; i <= getPos(N, M); i++) ans = max(ans, F.mat[0][i]); printf("%lld", ans); return 0; }
这道题算是一道矩阵递推的模板题吧。不是很了解矩阵乘法或者是矩阵递推加速原理的可以移步这篇 Wiki:矩阵 – OI Wiki.我们很快可以推出一个 DP 方程出来,其中\(i\)代表位数,\(j\)代表第一位所填的数:
\[dp[i][j] = \sum^{j+2}_{k=j-2}dp[i-1][k]\]
然后,我们可以根据这个来推出一个递推矩阵:
\[\left[ \begin{array}{ccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\
\end{array} \right]\]
初始矩阵是这样的:
\[\left[ \begin{array}{ccc}
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{array} \right]\]
代码如下:
// P2106.cpp #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define ll long long using namespace std; const ll mod = 1000000007; struct matrix { ll mat[10][10]; matrix() { memset(mat, 0, sizeof(mat)); } matrix operator*(const matrix &ma) const { matrix empt; for (ll i = 0; i < 10; i++) for (ll j = 0; j < 10; j++) for (ll k = 0; k < 10; k++) empt.mat[i][j] = (empt.mat[i][j] + mat[i][k] * ma.mat[k][j] % mod) % mod; return empt; } matrix operator^(const ll &num) const { ll tim = num; matrix pre = *(this); matrix tmp; for (ll i = 0; i < 10; i++) tmp.mat[i][i] = 1; while (tim) { if (tim & 1) tmp = tmp * pre; pre = pre * pre; tim >>= 1; } return tmp; } } premat, Dmat; int main() { ll k; scanf("%lld", &k); if (k == 1) { printf("%lld", 10); return 0; } for (ll i = 1; i < 10; i++) premat.mat[0][i] = 1; for (ll i = 0; i < 10; i++) for (ll j = i - 2; j <= i + 2; j++) { if (j < 0) continue; if (j > 9) break; Dmat.mat[j][i] = 1; } Dmat = Dmat ^ (k - 1); premat = premat * Dmat; ll ans = 0; for (ll i = 0; i < 10; i++) ans += premat.mat[0][i], ans %= mod; printf("%lld", ans); return 0; }