个人空间 - AcWing

球场鸡王

关注数

粉丝数

阅读量

2354

+关注发消息

离线：9小时前

最近来访(195)

种花家的兔兔

mzbgf

落月成孤倚灬

垫抽底风

予我渡北川

yyjjhh2010

JackWei

忘打周赛Duck

呼呼yyy

Anohgy

JcWing

胡尔摩斯

明日原由纪

LH_95

垫底抽風

YFJ

NZX

Egbert-Lannister.

M.R

Finn2009

活动打卡代码 AcWing 233. 换教室

球场鸡王
3天前

                #include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <functional>
#include <iomanip>
using namespace std;
const int N = 2010, M = 310;
const double INF = 1000000000.0;
int n, m, v, e, a[N], b[N];
double d[M][M], f[N][N][2], k[N], ans = INF;
void floyd() {
    for (int i = 1; i <= v; ++i) {
        for (int j = 1; j <= v; ++j) {
            for (int l = 1; l <= v; ++l) {
                d[j][l] = d[l][j] = min(d[j][l], d[j][i] + d[i][l]);
            }
        }
    }
}
int main() {
    cin >> n >> m >> v >> e;
    for (int i = 1; i <= v; ++i) {
        for (int j = 1; j <= v; ++j) {
            d[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int l = 0; l < 2; ++l) {
                f[i][j][l] = INF;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
    }
    for (int i = 1; i <= v; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < e; ++i) {
        int start, end;
        double length;
        cin >> start >> end >> length;
        d[start][end] = d[end][start] = min(d[start][end], length);
    }
    floyd();
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            f[i][j][0] = min(f[i-1][j][0] + d[a[i-1]][a[i]], f[i-1][j][1] + (1 - k[i-1]) * d[a[i-1]][a[i]] + k[i-1] * d[b[i-1]][a[i]]);
            if (j) {
                f[i][j][1] = min(f[i-1][j-1][0] + d[a[i-1]][a[i]] * (1 - k[i]) + d[a[i-1]][b[i]] * k[i], f[i-1][j-1][1] + d[a[i-1]][a[i]] * (1 - k[i-1]) * (1 - k[i]) + d[a[i-1]][b[i]] * (1 - k[i-1]) * k[i] + d[b[i-1]][a[i]] * k[i-1] * (1 - k[i]) + d[b[i-1]][b[i]] * k[i-1] * k[i]);
            }
        }
    }
    for (int i = 0; i <= m; ++i) {
        ans = min(ans, min(f[n][i][0], f[n][i][1]));
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

            

活动打卡代码 AcWing 222. 青蛙的约会

球场鸡王
3天前

                #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod(ll a, ll b) {
    return (a % b + b) % b;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}
int main() {
    ll x, y, m, n, l, p, q, d, t, k;
    cin >> x >> y >> m >> n >> l;
    p = mod(n - m, l), q = mod(x - y, l);
    d = exgcd(p, l, t, k);
    if (q % d) {
        cout << "Impossible" << endl;
    } else {
        cout << mod(q / d * t, l / d) << endl;
    }
    return 0;
}

            

活动打卡代码 AcWing 221. 龙哥的问题

球场鸡王
3天前

                #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, ans = 0;
ll phi(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        int k = 0;
        while (x % i == 0) {
            x /= i;
            k++;
        }
        if (k) {
            res = res / i * (i - 1);
        }
    }
    if (x > 1) {
        res = res / x * (x - 1);
    }
    return res;
}
int main() {
    cin >> n;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ans += i * phi(n/i);
            if (i != n / i) {
                ans += n / i * phi(i);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

            

活动打卡代码 AcWing 230. 排列计数

球场鸡王
6天前

                #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, N = 1000010;
ll t, n, m, fac[N], inv[N], f[N];
ll qmi(ll a, ll b, ll p) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
    }
    return ans;
}
ll C(ll a, ll b) {
    return fac[a] * inv[b] % mod * inv[a-b] % mod;
}
void init() {
    f[0] = 1, f[1] = 0, f[2] = 1, fac[0] = 1, fac[1] = 1, fac[2] = 2, inv[0] = 1, inv[1] = 1, inv[2] = qmi(2, mod - 2, mod);
    for (int i = 3; i < N; ++i) {
        f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod;
        fac[i] = fac[i-1] * i % mod;
        inv[i] = qmi(fac[i], mod - 2, mod);
    }
}
int main() {
    init();
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", n <= m ? 1 : C(n, m) * f[n-m] % mod);
    }
    return 0;
}

            

活动打卡代码 AcWing 226. 233矩阵

球场鸡王
6天前

                #include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <functional>
using namespace std;
const int N = 20, mod = 1e7 + 7;
long long n, m, f[N], e[N][N];
void mul(long long a[N], long long b[N][N]) {
    long long c[N];
    memset(c, 0, sizeof c);
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            c[i] += a[j] * b[j][i];
            c[i] %= mod;
        }
    }
    memcpy(a, c, sizeof c);
}
void selfMul(long long a[N][N]) {
    long long c[N][N];
    memset(c, 0, sizeof c);
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                c[i][j] += a[i][k] * a[k][j];
                c[i][j] %= mod;
            }
        }
    }
    memcpy(a, c, sizeof c);
}
void qmi(int a) {
    for (; a; a >>= 1) {
        if (a & 1) {
            mul(f, e);
        }
        selfMul(e);
    }
}
int main() {
    while (cin >> n >> m) {
        n++;
        e[0][0] = 1, e[1][0] = 0, f[0] = 1, f[1] = 23;
        for (int i = 2; i <= n; ++i) {
            cin >> f[i];
        }
        for (int i = 1; i <= n; ++i) {
            e[0][i] = 3, e[1][i] = 10;
        }
        for (int i = 2; i <= n; ++i) {
            for (int j = i; j <= n; ++j) {
                e[i][j] = 1;
            }
        }
        qmi(m);
        cout << f[n] << endl;
    }
    return 0;
}

            

活动打卡代码 AcWing 225. 矩阵幂求和

球场鸡王
6天前

                #include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <functional>
using namespace std;
const int N = 50;
struct node {
    int matrix[N][N];
    node() {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                this->matrix[i][j] = 0;
            }
        }
    }
};
node e, a, ans;
int n, k, m;
node add(node b, node c) {
    node d;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d.matrix[i][j] = b.matrix[i][j] + c.matrix[i][j];
            d.matrix[i][j] %= m;
        }
    }
    return d;
}
node mul(node b, node c) {
    node d;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int l = 0; l < n; ++l) {
                d.matrix[i][j] += b.matrix[i][l] * c.matrix[l][j];
                d.matrix[i][j] %= m;
            }
        }
    }
    return d;
}
node qmi(node b, int c) {
    node d = e;
    for (; c; c >>= 1) {
        if (c & 1) {
            d = mul(d, b);
        }
        b = mul(b, b);
    }
    return d;
}
node f(int p) {
    if (p == 1) {
        return a;
    } else if (p % 2) {
        return add(a, mul(a, f(p - 1)));
    } else {
        return mul(add(e, qmi(a, p / 2)), f(p / 2));
    }
}
int main() {
    cin >> n >> k >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a.matrix[i][j];
        }
        e.matrix[i][i] = 1;
    }
    ans = f(k);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << ans.matrix[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}



            

活动打卡代码 AcWing 223. 阿九大战朱最学

球场鸡王
6天前

                #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
ll n, M = 1, ans = 0, a[N], b[N];
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        M *= a[i];
    }
    for (int i = 0; i < n; ++i) {
        ll m = M / a[i], t, x, k;
        k = exgcd(m, a[i], t, x);
        ans += m * t % M * b[i];
        ans %= M;
    }
    cout << (ans + M) % M;
    return 0;
}

            

活动打卡代码 AcWing 220. 最大公约数

球场鸡王
6天前

                #include <bits/stdc++.h>
using namespace std;
const int N = 10000010;
bool st[N];
long long primes[N], sum[N], phi[N], idx = 0, n, ans = 0;
void get_prime(int x) {
    memset(st, false, sizeof st);
    phi[1] = 1, sum[0] = 0;
    for (int i = 2; i <= x; ++i) {
        if (!st[i]) {
            primes[idx++] = i, phi[i] = i - 1;
        }
        for (int j = 0; j < idx && i * primes[j] <= x; ++j) {
            st[i*primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[primes[j]*i] = phi[i] * primes[j];
                break;
            } else {
                phi[primes[j]*i] = phi[i] * (primes[j] - 1);
            }
        }
    }
    for (int i = 1; i <= x; ++i) {
        sum[i] = sum[i-1] + phi[i];
    }
}
int main() {
    get_prime(N-1);
    cin >> n;
    for (int i = 0; primes[i] <= n; ++i) {
        ans += 2 * sum[n / primes[i]] - 1;
    }
    cout << ans;
    return 0;
}

            

题解 AcWing 230. 排列计数

球场鸡王
7天前

题目描述

求有多少种长度为 $n$ 的序列 $A$，满足以下条件：

$1∼n$ 这 $n$ 个数在序列中各出现了一次。
若第 $i$ 个数 $A_i$ 的值为 $i$，则称 $i$ 是稳定的，序列恰好有 $m$ 个数是稳定的。

由于满足条件的序列可能很多，所以请你将序列数对 $10^9+7$ 取模后输出。

输入格式

第一行一个数 $T$，表示有 $T$ 组数据。

接下来 $T$ 行，每行两个整数 $n、m$。

输出格式

输出 $T$ 行，每行一个整数，表示求出的序列数对 $10^9+7$ 取模后的值。

数据范围

$T \leq 500000,n \leq 1000000,m \leq 1000000$

输入样例:

输出样例:

算法

非常经典的错排问题。

首先，选出 $m$ 个数当稳定的数，共有 $C_n^m$ 种选法。

剩下 $n-m$ 个数就是错排问题。设 $f_i$ 表示 $i$ 个数的错排方案数，那么，设 $i$ 放在了第 $j$ 个位置，那对于 $j$，显然有 $i-1$ 种选择。我们可以分两种情况：

把 $j$ 放在第 $i$ 个位置，这样就形成了 $i-2$ 个数字的错排。
把 $j$ 前 $i-1$ 个位置，这样就形成了 $i-1$ 个数字的错排。

综上所述，我们可以得到递推式 $f_i=(i-1) \times (f_{i-1}+f_{i-2})$，最后 $f_{n-m} \times C_n^m$ 就是答案。

时间复杂度

$O(nlog_n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, N = 1000010;
ll t, n, m, fac[N], inv[N], f[N];
ll qmi(ll a, ll b, ll p) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
    }
    return ans;
}
ll C(ll a, ll b) {
    return fac[a] * inv[b] % mod * inv[a-b] % mod;
}
void init() {
    f[0] = 1, f[1] = 0, f[2] = 1, fac[0] = 1, fac[1] = 1, fac[2] = 2, inv[0] = 1, inv[1] = 1, inv[2] = qmi(2, mod - 2, mod);
    for (int i = 3; i < N; ++i) {
        f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod;
        fac[i] = fac[i-1] * i % mod;
        inv[i] = qmi(fac[i], mod - 2, mod);
    }
}
int main() {
    init();
    scanf("%lld", &t);
    while (t--) {
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", n <= m ? 1 : C(n, m) * f[n-m] % mod);
    }
    return 0;
}

题解 AcWing 225. 矩阵幂求和

球场鸡王
7天前

题目描述

给定 $n \times n$ 矩阵 $A$ 和正整数 $k$，求和 $S=A+A^2+A^3+…+A^k$。

输入格式

输入只包含一个测试用例。

第一行输入包含三个正整数 $n$，$k$ 和 $m$。

接下来 $n$ 行，每行包含 $n$ 个非负整数（均不超过 $32,768$），用以描绘矩阵 $A$。

输出格式

按与描述矩阵 $A$ 相同的方式，输出将 $S$ 中所有元素对 $m$ 取模后得到的矩阵。

数据范围

$1 \leq n \leq 30 \\
1 \leq k \leq 10^9 \\
1 \leq m \leq 10^4$

输入样例:

2 2 4
0 1
1 1

输出样例:

1 2
2 3

算法

暴力计算显然是不行的，因为 $k$ 有 $10^9$。

于是我们拆解一下这个算式：

当 $k$ 是偶数时，设 $e$ 为矩阵常数 $1$，也就是“对角矩阵”：

$
\quad A+A^2+A^3+…+A^k \\
=A+A^2+A^3+…+A^{\frac{k}{2}}+A^{\frac{k}{2}+1}+…+A^k \\
=A+A^2+A^3+…+A^{\frac{k}{2}}+A^{\frac{k}{2}}(A+A^2+A^3+…+A^{\frac{k}{2}}) \\
=(e+A^{\frac{k}{2}})(A+A^2+A^3+…+A^{\frac{k}{2}})
$

当 $k$ 是奇数时，不妨设 $s_k=A+A^2+A^3+…+A^k$，$n$ 是一个非负整数：

$
\quad s_k \\
=s_{2n+1} \\
=A+A^2+A^3+…+A^{2n+1} \\
=A+A(A+A^2+A^3+…+A^{2n}) \\
=A+A \times s_{2n} \\
=A+A \times s_{k-1}
$

我们只需要按步骤递归出结果，进行矩阵加法、乘法和快速幂就行了。

C++ 代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <functional>
using namespace std;
const int N = 50;
struct node {
    int matrix[N][N];
    node() {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                this->matrix[i][j] = 0;
            }
        }
    }
};
node e, a, ans;
int n, k, m;
node add(node b, node c) {
    node d;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d.matrix[i][j] = b.matrix[i][j] + c.matrix[i][j];
            d.matrix[i][j] %= m;
        }
    }
    return d;
}
node mul(node b, node c) {
    node d;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int l = 0; l < n; ++l) {
                d.matrix[i][j] += b.matrix[i][l] * c.matrix[l][j];
                d.matrix[i][j] %= m;
            }
        }
    }
    return d;
}
node qmi(node b, int c) {
    node d = e;
    for (; c; c >>= 1) {
        if (c & 1) {
            d = mul(d, b);
        }
        b = mul(b, b);
    }
    return d;
}
node f(int p) {
    if (p == 1) {
        return a;
    } else if (p % 2) {
        return add(a, mul(a, f(p - 1)));
    } else {
        return mul(add(e, qmi(a, p / 2)), f(p / 2));
    }
}
int main() {
    cin >> n >> k >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a.matrix[i][j];
        }
        e.matrix[i][i] = 1;
    }
    ans = f(k);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << ans.matrix[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

题目描述

输入格式

输出格式

数据范围

输入样例:

输出样例:

算法

时间复杂度

C++ 代码

0 评论

题目描述

输入格式

输出格式

数据范围

输入样例:

输出样例:

算法

C++ 代码

0 评论