西南财经大学·奇点工作室·程序设计部 暑期训练营 第四次课后习题题解

A. 开心的涂刷

题目链接：A. 开心的涂刷

考察知识点：数学、快速幂

$nn$ 个格子处于同一排，忽略限制最多有 $m^{n}m^n$ 种涂法。

考虑让小明不开心的涂法，易知这样的涂法有 $m(m-1{)}^{n-1}m(m-1)^\{n-1\}$ 种，因为第一个格子可以从 $mm$ 种颜色中任选，后面的格子只能从与上一个格子不同的 $m-1m-1$ 种颜色中任选。

最终答案即为 $m^n-m(m-1{)}^{n-1}m^n-m(m-1)^\{n-1\}$，用快速幂优化即可。

时间复杂度：$O(\log n)O(\backslash log\; n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007

ll qpw(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    ll n, m;
    cin >> n >> m;
    m %= MOD;
    ll ans = (qpw(m, n) - m * qpw(m - 1, n - 1) % MOD + MOD) % MOD;
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

B. 银行存款

题目链接：B. 银行存款

考察知识点：枚举

数据范围较小，套三重循环枚举即可。

时间复杂度：$O(n^3)O(n^3)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    double r1, r2, r3, r5;
    cin >> n >> r1 >> r2 >> r3 >> r5;
    double ans = 0;
    for (int x5 = 0; x5 <= n / 5; x5++)
        for (int x3 = 0; x3 <= n / 3; x3++)
            for (int x2 = 0; x2 <= n / 2; x2++)
            {
                int x1 = n - x2 * 2 - x3 * 3 - x5 * 5;
                if (x1 < 0)
                    continue;
                double tmp = pow(1 + r1, x1) * pow(1 + r2, x2 * 2) * pow(1 + r3, x3 * 3) * pow(1 + r5, x5 * 5);
                ans = max(ans, tmp);
            }
    cout << fixed << setprecision(5) << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

你也可以用一下快速幂

C. 用来作弊的药水

题目链接：C. 用来作弊的药水

考察知识点：快速幂

题目很长，但是意思很简单，就是判断 $x^{a}x^a$ 和 $y^{b}y^b$ 是否相等。

使用快速幂优化即可。

时间复杂度：$O(\log a+\log b)O(\backslash log\; a+\backslash log\; b)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll qpw(ll a, ll b, ll mod = 1e9 + 7)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}

void solve()
{
    ll x, a, y, b;
    cin >> x >> a >> y >> b;
    if (qpw(x, a) == qpw(y, b))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. 两条斜线

题目链接：D. 两条斜线

考察知识点：数学

斜率为 $11$ 的直线通式为 $y=x+by=x+b$，斜率为 $-1-1$ 的直线通式为 $y=-x+by=-x+b$。

因此我们可以通过截距 $b=y-xb=y-x$ 或 $b=y+xb=y+x$ 来确定直线并统计点的个数。

两条直线可能有交点被统计，最后要注意去重。

时间复杂度：$O(n^2)O(n^2)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 1005

void solve()
{
    int n, cnt = 0, x[N], y[N];
    cin >> n;
    map<int, set<int>> mp[2];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n; i++)
        cin >> y[i];
    for (int i = 0; i < n; i++)
    {
        mp[0][x[i] + y[i]].insert(cnt);
        mp[1][x[i] - y[i]].insert(cnt++);
    }
    int ans = 0;
    for (auto &i : mp[0])
        for (auto &j : mp[1])
        {
            int tmp = i.second.size() + j.second.size();
            for (auto &k : i.second)
                if (j.second.count(k))
                    tmp--;
            ans = max(ans, tmp);
        }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

E. ZQ的睡前故事

题目链接：E. ZQ的睡前故事

考察知识点：数学

经典的约瑟夫环问题，模拟即可，下面的代码提供了一种思路。

时间复杂度：$O(nk)O(nk)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (int i = 0; i < n; i++)
        a[i] = i + 1;
    int cnt = n, x = 0, cur = 0;
    while (cnt)
    {
        if (a[cur] != 0)
            x++;
        if (x == k)
        {
            cout << a[cur] << " ";
            a[cur] = 0;
            cnt--;
            x = 0;
        }
        cur = (cur + 1) % n;
    }
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

也可以用循环链表模拟。

F. 异或和

题目链接：F. 异或和

考察知识点：数学、逆元

一个点到另一个点的曼哈顿距离可以分解为 $xx$ 与 $yy$ 方向上的分量，同一行的点到另一点的 $xx$ 分量相同，同一列的点到另一点的 $yy$ 分量相同。

因此，我们可以分别枚举每一行和每一列，统计对应的 $xx$ 分量和 $yy$ 分量。对于点 $(i,j)(i,j)$，它的期望曼哈顿距离为第 $ii$ 行的 $xx$ 分量与第 $jj$ 列的 $yy$ 分量之和。

然后枚举每个位置的点计算期望曼哈顿距离的异或和即可。

计算期望时注意使用逆元。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 2005
#define MOD 1000000007

int board[N][N], x[N], y[N];
int row[N], col[N];

ll qpw(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    int fenMu = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            board[i][j] = s[j - 1] - '0';
            fenMu += board[i][j];
            row[i] += board[i][j];
            col[j] += board[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            x[i] += row[j] * abs(i - j);
            x[i] %= MOD;
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            y[i] += col[j] * abs(i - j);
            y[i] %= MOD;
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int fenZi = (x[i] + y[j]) % MOD;
            ans ^= fenZi * qpw(fenMu, MOD - 2) % MOD;
        }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

G. 取手机

题目链接：G. 取手机

考察知识点：数学

事实上，问题相当于给定 $aa$ 台 iPhoneX 和 $bb$ 台 S8，然后随机排列，问你第 $kk$ 台是 S8 的概率。

很明显，答案与 $kk$ 无关，为 $\frac{b}{a+b}\backslash frac\{b\}\{a+b\}$。

时间复杂度：$O(1)O(1)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    ll a, b, k;
    cin >> a >> b >> k;
    cout << fixed << setprecision(3);
    cout << 1.0 * b / (a + b) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

H. 序列求和

题目链接：H. 序列求和

考察知识点：数学、逆元

证明方法有很多种，详情请见：

1²+2²+…+n²求和公式的推导有哪些方法? - 知乎

注意除 $66$ 时要使用逆元。

时间复杂度：$O(1)O(1)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007

ll qpw(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n = 1, inv6 = qpw(6, MOD - 2);
    // cin >> t;
    while (cin >> n)
    {
        n %= MOD;
        ll ans = n * (n + 1) % MOD * ((2 * n + 1) % MOD) % MOD;
        cout << ans % MOD * inv6 % MOD << endl;
    }
    return 0;
}