跳到主要内容

矩阵乘法和组合计数

AcWing 1304. 佳佳的斐波那契​

题目​

佳佳对数学，尤其对数列十分感兴趣。 在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。 例如用 S(n) 表示 Fibonacci 前 n 项和 modm 的值，即 S(n)=(F1+F2+…+Fn)modm ，其中 F1=F2=1,Fi=Fi−1+Fi−2 。 可这对佳佳来说还是小菜一碟。 终于，她找到了一个自己解决不了的问题。 用 T(n)=(F1+2F2+3F3+…+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。 现在佳佳告诉你了一个 n 和 m ，请求出 T(n) 的值。

思路​

image-20240818225720867

latex代码无法渲染：

$S_n=F_1+F_2+...+F_n$
$T_n=F_1+2F_2+...+nF_n$
$nS_n=nF_1+nF_2+...+nF_n$
所以

$nS_n-T_n=(n-1)F_1+(n-2)F_2+...+F_{n-1}$
$(n+1)S_{n+1}-T_{n+1}=nF_1+(n-1)F_2+...+2F_{n-1}+Fn$
令$P_n=nS_n-T_n$,所以$P_{n+1}-P_n=F_1+F_2+...F_n=S_n$
$\begin{bmatrix}
f_n & f_{n+1} &S_n&P_n
\end{bmatrix}*\begin{bmatrix}
0&1&0&0 \\
1&1&1&0\\
0&0&1&1 \\
0&0&0&1
\end{bmatrix}
=
\begin{bmatrix}
f_{n+1} & f_{n+2} &S_{n+1}&P_{n+1}
\end{bmatrix}$
令$A=\begin{bmatrix}
0&1&0&0 \\
1&1&1&0\\
0&0&1&1 \\
0&0&0&1
\end{bmatrix}$

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 4;

int n, m;

void mul(int res[][N], int a[][N], int b[][N]) {
    int temp[N][N] = {0};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                temp[i][j] = (temp[i][j] + (ll) a[i][k] * b[k][j]) % m;
            }
        }
    }
    ::memcpy(res, temp, sizeof temp);

}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin >> n >> m;
    int f1[N][N] = {1, 1, 1, 0};
    int A[N][N] = {
            {0, 1, 0, 0},
            {1, 1, 1, 0},
            {0, 0, 1, 1},
            {0, 0, 0, 1}
    };
    int k = n - 1;
    while (k){
        if (k&1) mul(f1,f1,A);
        mul(A,A,A);
        k>>=1;
    }
    pr((((ll) n * f1[0][2] - f1[0][3]) % m + m) % m)


    return 0;
}

AcWing 1305. GT考试​

题目​

阿申准备报名参加 GT 考试，准考证号为 n 位数 X1X2⋯Xn ，他不希望准考证号上出现不吉利的数字。 他的不吉利数字 A1A2⋯Am 有 m 位，不出现是指 X1X2⋯Xn 中没有恰好一段等于 A1A2⋯Am ，A1 和 X1 可以为 0

思路​

状态表示：f[i][j]表示长度是i，且不包含不吉利字符串，且，末尾部分与不吉利数字相同的长度是j的所有字符串的集合的数量 状态计算：f[i+1][k]=a[0][k]f[i+1][k]=a[0][k]

代码​

AcWing 1307. 牡牛和牝牛​

题目​

思路​

状态表示：f[i]表示所有长度是i的且以1结尾的字符串数量

代码​

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10,mod=5000011;

int n,k;
int f[N],s[N];

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n>>k;
    f[0]=s[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=s[max(i-k-1,0)];
        s[i]=(s[i-1]+f[i])%mod;
    }
    pr(s[n])
    return 0;
}

0%