头像

清风qwq




在线 


最近来访(302)
用户头像
Nicoppa
用户头像
静夜@
用户头像
月亮供电不足
用户头像
重生之幻影
用户头像
ㅤ_049
用户头像
Eric_00
用户头像
星尘流天
用户头像
acwing_5735
用户头像
AcWing2AK
用户头像
yankai
用户头像
顽童
用户头像
acwing_gza
用户头像
lsz_
用户头像
Jun不见
用户头像
超爱三玖
用户头像
身心都是摇曳鳗
用户头像
dqsjysgs
用户头像
wshzt
用户头像
@王
用户头像
一万小时定律


清风qwq
2分钟前

$Code$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL C(int a)
{
    return (LL)a * (a - 1) * (a - 2) / 6; 
}

LL gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n, m;
    cin >> n >> m;

    n ++ , m ++ ;

    LL ans = C(n * m) - C(n) * m - C(m) * n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            ans -= 2ll * (n - i) * (m - j) * (gcd(i, j) - 1);

    cout << ans;        

    return 0;
}


活动打卡代码 AcWing 1310. 数三角形

清风qwq
2分钟前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL C(int a)
{
    return (LL)a * (a - 1) * (a - 2) / 6; 
}

LL gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n, m;
    cin >> n >> m;

    n ++ , m ++ ;

    LL ans = C(n * m) - C(n) * m - C(m) * n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            ans -= 2ll * (n - i) * (m - j) * (gcd(i, j) - 1);

    cout << ans;        

    return 0;
}



清风qwq
11小时前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5010, P = 100003;

int mul[N], divi[N];

int FastPower(int a, int b)
{
    if (b == 1)return a;

    int t = FastPower(a, b / 2);
    if (b & 1)return (LL)t * t % P * a % P;
    return (LL)t * t % P;
}

int A(int a, int b)
{
    if (a < b)return 0;
    return (LL)mul[a] * divi[a - b] % P;
}

int C(int a, int b)
{
    if (a < b)return 0;
    return (LL)mul[a] * divi[a - b] % P * divi[b] % P;
}

int T(int n, int m, int k)
{
    return (LL)C(n, k) * A(m, k) % P;
}

int main()
{
    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    mul[0] = divi[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        mul[i] = (LL)mul[i - 1] * i % P;
        divi[i] = (LL)divi[i - 1] * FastPower(i, P - 2) % P;
    }

    LL res = 0;
    for (int i = 0; i <= k; i ++ )
        res = (res + (LL)T(a, b, i) * T(a + c - i, d, k - i) % P) % P;

    printf("%d", res);

    return 0;
}


活动打卡代码 AcWing 1309. 车的放置

清风qwq
11小时前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5010, P = 100003;

int mul[N], divi[N];

int FastPower(int a, int b)
{
    if (b == 1)return a;

    int t = FastPower(a, b / 2);
    if (b & 1)return (LL)t * t % P * a % P;
    return (LL)t * t % P;
}

int A(int a, int b)
{
    if (a < b)return 0;
    return (LL)mul[a] * divi[a - b] % P;
}

int C(int a, int b)
{
    if (a < b)return 0;
    return (LL)mul[a] * divi[a - b] % P * divi[b] % P;
}

int T(int n, int m, int k)
{
    return (LL)C(n, k) * A(m, k) % P;
}

int main()
{
    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    mul[0] = divi[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        mul[i] = (LL)mul[i - 1] * i % P;
        divi[i] = (LL)divi[i - 1] * FastPower(i, P - 2) % P;
    }

    LL res = 0;
    for (int i = 0; i <= k; i ++ )
        res = (res + (LL)T(a, b, i) * T(a + c - i, d, k - i) % P) % P;

    printf("%d", res);

    return 0;
}



$Code$

// O | O O O
//C_{n - 1}^{k - 1} = k * ... * (n - 1)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 5010;

int ans[N], len;

int FastPower(int a, int b)
{
    if (b == 1)return a;

    int t = FastPower(a, b / 2);
    if (b & 1)return (LL)t * t % 1000 * a % 1000;
    return (LL)t * t % 1000;
}

void mul(int c)
{
    for (int i = 1; i <= len; i ++ )
        ans[i] *= c;

    for (int i = 1; i <= len; i ++ )
    {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }

    while (ans[len + 1])
    {
        len ++ ;
        ans[len + 1] = ans[len] / 10;
        ans[len] %= 10;
    }
}

void div(int c)
{
    int r = 0;
    for (int i = len; i >= 1; i -- )
    {
        int d = (ans[i] + r * 10) / c;
        r = (ans[i] + r * 10) % c;
        ans[i] = d;
    }

    while (!ans[len])len -- ;
}

void print()
{
    for (int i = len; i >= 1; i -- )
        cout<<ans[i];   
    puts("");    
}

int main()
{
    int n, m;
    cin >> n >> m;

    m = FastPower(m % 1000, m % 1000);

    ans[1] = len = 1;
    for (int i = m - n + 1; i < m; i ++ )mul(i);
    for (int i = 1; i < n; i ++ )div(i);

    print();

    return 0;
}


活动打卡代码 AcWing 1308. 方程的解

// O | O O O
//C_{n - 1}^{k - 1} = k * ... * (n - 1)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 5010;

int ans[N], len;

int FastPower(int a, int b)
{
    if (b == 1)return a;

    int t = FastPower(a, b / 2);
    if (b & 1)return (LL)t * t % 1000 * a % 1000;
    return (LL)t * t % 1000;
}

void mul(int c)
{
    for (int i = 1; i <= len; i ++ )
        ans[i] *= c;

    for (int i = 1; i <= len; i ++ )
    {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }

    while (ans[len + 1])
    {
        len ++ ;
        ans[len + 1] = ans[len] / 10;
        ans[len] %= 10;
    }
}

void div(int c)
{
    int r = 0;
    for (int i = len; i >= 1; i -- )
    {
        int d = (ans[i] + r * 10) / c;
        r = (ans[i] + r * 10) % c;
        ans[i] = d;
    }

    while (!ans[len])len -- ;
}

void print()
{
    for (int i = len; i >= 1; i -- )
        cout<<ans[i];   
    puts("");    
}

int main()
{
    int n, m;
    cin >> n >> m;

    m = FastPower(m % 1000, m % 1000);

    ans[1] = len = 1;
    for (int i = m - n + 1; i < m; i ++ )mul(i);
    for (int i = 1; i < n; i ++ )div(i);

    print();

    return 0;
}


活动打卡代码 AcWing 1307. 牡牛和牝牛

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, P = 5000011;

long long f[N], s[N];

int main()
{
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= k + 1; i ++ )f[i] = 1, s[i] = i;

    for (int i = k + 2; i <= n; i ++ )
    {
        f[i] = (s[i - k - 1] + 1) % P;
        s[i] = (s[i - 1] + f[i]) % P;
    }

    cout<<(s[n] + 1) % P;

    return 0;
}


分享 矩阵乘法

Better reading experience

数学知识之矩阵乘法

$矩阵乘法是一种高效的算法可以把一些一维递推优化到log(n),是一种应用性极强的算法。$

$矩阵,是线性代数中的基本概念之一。$

$矩阵乘法可以解决从一个状态转换到另一个状态的动态规划问题$


$这里例举一个斐波那契数列求和的问题$

$第i个状态数组标识为$

状态序号 $第i个数$ $第 i + 1 个数$ $ 前i个数的和$
$i$ $f[i]$ $f[i + 1]$ $S[i]$
$i + 1$ $f[i + 1] $ $f[i + 2] =f[i] + f[i + 1]$ $ S[i + 1] = S[i] + f[i + 1] $

$现有一个矩阵A[N][N]$

$能使F[i] 变换为 F[i+1]$
$f[i + 1] = f[i] \times 0 + f[i + 1] \times 1 + S[i] \times 0, 第一列[0,1,0]$
$f[i + 2] =f[i] \ times 1 + f[i + 1] \times 1 + S[i] \times 0, 第二列[1,1,0]$
$ S[i + 1] =f[i] \ times 0 + f[i + 1] \times 1 + S[i] \times 1, 第三列[0,1,1]$

$
A=
\left[
\begin{matrix}
0 & 1 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1 \\
\end{matrix}
\right]
$


序列 乘 矩阵

$按照上列求出的A矩阵$

$依次求出每一个乘出来的值$

$F[i + 1][j] = \sum _{k = 0}^{k < N}F[i][k] \times A[k][j] (0 \leq j < n)$

$Code$

void mul(int c[N], int a[N], int b[N][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);     
}

矩阵乘矩阵

$由于每次把一个序列和矩阵相乘,想要达到目标序列的时间复杂度是O(n)$

$因为每一次乘的矩阵都是常量, 所以可以用快速幂,来优化计算A^n,时间复杂度O(log_2n)$

$那么怎样才能把两个矩阵相乘呢?$

$矩阵相乘,设A \times B = C$

$那么序列F \times A \times B = F \times C$

$对于C中的每一个数C[i][j]表示F \times A \times B 的第j位数是有多少个F[i]组成的$

$在F \times A 中 的 每一位数AF[k] 中包含了 A[i][k]个F[i]$

$对于 每一位 AF[k] 包含的F[i] ,在ABF[j]中都贡献了 B[k][j]倍$

$那么C[i][j] = \sum _{k=0}^{k<N} A[i][k] \times B[k][j]$

$Code$

void mul(int c[N][N], int a[N][N], int b[N][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(c, temp, sizeof temp);   
}

$Code$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = ;//...

int n, m;

void mul(int c[N], int a[N], int b[N][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);     
}

void mul(int c[N][N], int a[N][N], int b[N][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(c, temp, sizeof temp);
}

void print()
{
    //...
}

int main()
{
    cin >> n >> m;

    int f[N] = {};//...
    int a[N][N] = {
        //...
    };

    n -- ;
    while (n)
    {
        if (n & 1)mul(f, f, a);
        mul(a, a, a);
        n >>= 1;
    }

    print();

    return 0;
}


分享 矩阵乘法

数学知识之矩阵乘法

$矩阵乘法是一种高效的算法可以把一些一维递推优化到log(n),是一种应用性极强的算法。$

$矩阵,是线性代数中的基本概念之一。$

$矩阵乘法可以解决从一个状态转换到另一个状态的动态规划问题$


$这里例举一个斐波那契数列求和的问题$

$第i个状态数组标识为$

状态序号 $第i个数$ $第 i + 1 个数$ $ 前i个数的和$
$i$ $f[i]$ $f[i + 1]$ $S[i]$
$i + 1$ $f[i + 1] $ $f[i + 2] =f[i] + f[i + 1]$ $ S[i + 1] = S[i] + f[i + 1] $

$现有一个矩阵A[N][N]$

$能使F[i] 变换为 F[i+1]$
$f[i + 1] = f[i] \times 0 + f[i + 1] \times 1 + S[i] \times 0, 第一列[0,1,0]$
$f[i + 2] =f[i] \ times 1 + f[i + 1] \times 1 + S[i] \times 0, 第二列[1,1,0]$
$ S[i + 1] =f[i] \ times 0 + f[i + 1] \times 1 + S[i] \times 1, 第三列[0,1,1]$

$
A=
\left[
\begin{matrix}
0 & 1 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1 \\
\end{matrix}
\right]
$


序列 乘 矩阵

$按照上列求出的A矩阵$

$依次求出每一个乘出来的值$

$F[i + 1][j] = \sum _{k = 0}^{k < N}F[i][k] \times A[k][j] (0 \leq j < n)$

$Code$

void mul(int c[N], int a[N], int b[N][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);     
}

矩阵乘矩阵

$由于每次把一个序列和矩阵相乘,想要达到目标序列的时间复杂度是O(n)$

$因为每一次乘的矩阵都是常量, 所以可以用快速幂,来优化计算A^n,时间复杂度O(log_2n)$

$那么怎样才能把两个矩阵相乘呢?$

$矩阵相乘,设A \times B = C$

$那么序列F \times A \times B = F \times C$

$对于C中的每一个数C[i][j]表示F \times A \times B 的第j位数是有多少个F[i]组成的$

$在F \times A 中 的 每一位数AF[k] 中包含了 A[i][k]个F[i]$

$对于 每一位 AF[k] 包含的F[i] ,在ABF[j]中都贡献了 B[k][j]倍$

$那么C[i][j] = \sum _{k=0}^{k<N} A[i][k] \times B[k][j]$

$Code$

void mul(int c[N][N], int a[N][N], int b[N][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(c, temp, sizeof temp);   
}

$Code$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = ;//...

int n, m;

void mul(int c[N], int a[N], int b[N][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);     
}

void mul(int c[N][N], int a[N][N], int b[N][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(c, temp, sizeof temp);
}

void print()
{
    //...
}

int main()
{
    cin >> n >> m;

    int f[N] = {};//...
    int a[N][N] = {
        //...
    };

    n -- ;
    while (n)
    {
        if (n & 1)mul(f, f, a);
        mul(a, a, a);
        n >>= 1;
    }

    print();

    return 0;
}


活动打卡代码 AcWing 1305. GT考试

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m, mod;
char str[N];
int ne[N];
int a[N][N];

void mul(int c[][N], int a[][N], int b[][N])
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < m; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < m; k ++ )
                t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;

    memcpy(c, t, sizeof t);
}

int qmi(int k)
{
    int f0[N][N] = {1};
    while (k)
    {
        if (k & 1) mul(f0, f0, a);
        mul(a, a, a);
        k >>= 1;
    }

    int res = 0;
    for (int i = 0; i < m; i ++ ) res = (res + f0[0][i]) % mod;
    return res;
}

int main()
{
    cin >> n >> m >> mod;
    cin >> str + 1;

    for (int i = 2, j = 0; i <= m; i ++ )
    {
        while (j && str[j + 1] != str[i]) j = ne[j];
        if (str[j + 1] == str[i]) j ++ ;
        ne[i] = j;
    }

    for (int j = 0; j < m; j ++ )
        for (int c = '0'; c <= '9'; c ++ )
        {
            int k = j;
            while (k && str[k + 1] != c) k = ne[k];
            if (str[k + 1] == c) k ++ ;
            if (k < m) a[j][k] ++ ;
        }

    cout << qmi(n) << endl;

    return 0;
}