「国家集训队 2011 扬天」解题报告

A – 等差子序列

因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。

继续阅读「国家集训队 2011 扬天」解题报告

Codeforces 1106F:Lunar New Year and a Recursive Sequence 题解

主要思路

哇这道题还是很神仙的。

首先,有递推式:

\[ 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;
}

CH3401:石头游戏题解

毒瘤思路

对,这道题是毒瘤题。首先,我们可以判定出,这些序列一定会在\(60s\)内全部从头开始,因为\(1,2,3,4,5,6\)的最大公倍数为\(60\)。之后,我们可以考虑把这些操作放入操作矩阵之中。操作矩阵的长宽都为\(n*m\)。具体的操作对应如下:

  • 在本题中,我们把一个二维的点映射为一个数,公式为\(num(i,j)=(i-1)m+j\)。
  • 对于把格子值设置为数字的操作:
    1. 首先把操作矩阵\(A[0][num(i,j)]\)设置为操作数。
    2. 之后,把矩阵\(A[num(i,j)][num(i,j)]\)设置为\(1\),这是为了使其在矩阵乘法中得到保留。
  • 而对于移动操作:
    • 如果是\(E\),那么把\(A[num(i,j)][num(i,j+1)]\)设置为一,以此类推

然后算出\(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;
}

P2106:Sam 数题解

这道题算是一道矩阵递推的模板题吧。不是很了解矩阵乘法或者是矩阵递推加速原理的可以移步这篇 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;
}