A - Count

题目链接

题意

题目就是中文，中翻中就没有必要了吧

思路

矩阵快速幂的入门模板题，掌握模板写一遍就可以了

代码

#include 
using namespace std;
typedef long long ll;
const int N = 100;
const ll mod = 123456789;
struct node
{
    ll a[6][6];
} A;

node mul(node a, node b)
{
    node x;
    memset(x.a, 0, sizeof(x.a));
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            for (int k = 0; k < 6; k++)
                x.a[i][j] = (x.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
    return x;
}
node ful(node a, ll n)
{
    node r;
    memset(r.a, 0, sizeof(r.a));
    for (int i = 0; i < 6; i++)
        r.a[i][i] = 1;
    while (n > 0)
    {
        if (n & 1)
            r = mul(r, a);
        n >>= 1;
        a = mul(a, a);
    }
    return r;
}

int main()
{
    A = {1, 2, 1, 3, 3, 1,
         1, 0, 0, 0, 0, 0,
         0, 0, 1, 3, 3, 1,
         0, 0, 0, 1, 2, 1,
         0, 0, 0, 0, 1, 1,
         0, 0, 0, 0, 0, 1};
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        if (n < 3)
        {
            cout << n << endl;
            continue;
        }
        node a = ful(A, n - 2);
        cout << (a.a[0][0] * 2 + a.a[0][1]  + a.a[0][2] * 8 + a.a[0][3] * 4 + a.a[0][4] * 2 + a.a[0][5]) % mod << endl;
    }

    return 0;
}

B - Tr A

题目链接

题意

 水题

思路

 套模板

代码

#include 
using namespace std;
const int mod = 9973;
struct node
{
    int m[10][10];
};
int n;
node mul(node a, node b)
{
    node x;
    memset(x.m, 0, sizeof(x.m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                x.m[i][j] = (x.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
    return x;
}

node ful(node a, int n)
{
    node r;
    memset(r.m, 0, sizeof(r.m));
    for (int i = 0; i < 10; i++)
        r.m[i][i] = 1;
    while (n > 0)
    {
        if (n & 1)
            r = mul(r, a);
        n >>= 1;
        a = mul(a, a);
    }
    return r;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int  k;
        cin >> n >> k;
        node A;
        memset(A.m, 0, sizeof(A.m));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> A.m[i][j];
        A = ful(A, k);
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += A.m[i][i];
        cout << ans % mod << endl;
    }
    return 0;
}

C - A Simple Math Problem

题目链接

题意

 Lele 现在正在考虑一个简单的函数 f(x)。

如果 x < 10 f(x) = x。
如果 x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)；
而 ai(0<=i<=9) 只能是 0 或 1 。

现在，我将给出 a0 ~ a9 和两个正整数 k 和 m，你能帮助lele计算 f(k)%m。

思路

 水题，按照题意构造矩阵就行了，最后计算乘于初始值有点麻烦，要注意

代码

#include 
using namespace std;
int mod;
struct node
{
    int m[10][10];
};
node mul(node a, node b)
{
    node x;
    memset(x.m, 0, sizeof(x.m));
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            for (int k = 0; k < 10; k++)
                x.m[i][j] = (x.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
    return x;
}

node ful(node a, int k)
{
    node r;
    memset(r.m, 0, sizeof(r.m));
    for (int i = 0; i < 10; i++)
        r.m[i][i] = 1;
    while (k > 0)
    {
        if (k & 1)
            r = mul(r, a);
        k >>= 1;
        a = mul(a, a);
    }
    return r;
}

int main()
{
    int n;
    while (scanf("%d%d", &n, &mod) != EOF)
    {

        int a1[10];
        for (int i = 0; i < 10; i++)
            cin >> a1[i];
        node A;
        A = {a1[0], a1[1], a1[2], a1[3], a1[4], a1[5], a1[6], a1[7], a1[8], a1[9],
             1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
             0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
             0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
             0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
             0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
             0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
             0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
             0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
             0, 0, 0, 0, 0, 0, 0, 0, 1, 0};
        if (n < 10)
        {
            int ans = 0;
            for (int i = 0; i < 10; i++)
                ans += (i * a1[i]);
            cout << ans << endl;
            continue;
        }
        A = ful(A, n - 9);
        int ans = 0;
        for (int i = 0; i < 10; i++)
            ans = (ans + A.m[0][i] * (9 - i)) % mod;
        cout << ans % mod << endl;
    }
    return 0;
}

D - Queuing

题目链接

题意

  现在我们定义“f”是女性的缩写，“m”是男性的缩写。如果队列的长度为 L，则有 2 ^L个队列。例如，如果 L = 2，则它们是 ff, mm, fm, mf 。如果存在 fmf 或 fff 子队列，我们??称其为 O-queue，否则为 E-queue。
你的任务是通过编写一个程序来计算长度为 L 的 E-queues mod M 的数量。

思路

构思巧妙的一道矩阵快速幂
我们设 f[i]">f [ i ] 表示有 i">i 个人时有多少种方案。
我们考虑第n">n个位置

• 假设第 n">n 位为 m">m ，那前 n−1">n?1 位是什么都行，有 f[n−1]">f [ n ? 1 ]种方案。
• 假设第 n">n 位为 f"> f，就有两种情况
  1. 第 n−1">n?1 位为 m">m，那 n−2">n?2位上一定要为m">m，第n−3">n?3位上就是随便选了，有f[n−3]">f[n?3]种方案
  2. 第 n−1">n?1 位为 f">f，那 n−2">n?2位一定要为m">m，且第n−3">n?3位上也要为m">m，那第n−4">n?4位就随便选了，有 f[n−4]">f[n?4]

综上所述，f[n]=f[n−1]+f[n−3]+f[n−4]">f[n]=f[n?1]+f[n?3]+f[n?4]
然后考虑矩阵加速

然后套矩阵快速幂就完了

代码

#include 
using namespace std;
int mod;
struct node
{
    int m[4][4];
};
node mul(node a, node b)
{
    node x;
    memset(x.m, 0, sizeof(x.m));
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                x.m[i][j] = (x.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
    return x;
}

node ful(node a, int k)
{
    node r;
    memset(r.m, 0, sizeof(r.m));
    for (int i = 0; i < 4; i++)
        r.m[i][i] = 1;
    while (k > 0)
    {
        if (k & 1)
            r = mul(r, a);
        k >>= 1;
        a = mul(a, a);
    }
    return r;
}

int main()
{
    int n;
    while (scanf("%d%d", &n, &mod) != EOF)
    {
        node A;
        A = {1, 0, 1, 1,
             1, 0, 0, 0,
             0, 1, 0, 0,
             0, 0, 1, 0};

        int a1[4] = {2, 4, 6, 9};
        if (n < 4)
        {

            cout << a1[n - 1] << endl;
            continue;
        }
        A = ful(A, n - 4);
        int ans = 0;
        for (int i = 0; i < 4; i++)
            ans = (ans + A.m[0][i] * a1[3 - i]) % mod;
        cout << ans % mod << endl;
    }
    return 0;
}