A – 楼房搭建

首先这题的 \(\Theta(n^3)\) 是很好写的，如果要写到 \(\Theta(n^2)\) 的分，我们可以观察到 DP 的过程其实是一个做后缀 min 的过程，所以优化完毕（当然也可以线性规划，但是很难写）。

正解比较神仙。考虑做到第 \(i\) 个时，考虑 \((2, 1)\) 的操作做满。显然这是局部最优解而不是全局最优解，然而我们考虑去反悔：考虑把 \((2, 1)\) 换成 \((1, 2)\)，在用额外的一个时间去做一个 \((1, 2)\)，那么我们可以在 \(i – 1\) 不动的情况下让 \(i\) 加上三个单位。其他的反悔方式类似。

大概就是这样的思路，我们可以记录上一次的次数然后贪心的换即可。

// building.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, hi[MAX_N], ai[MAX_N];

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

void fileIO()
{
    freopen("building.in", "r", stdin);
    freopen("building.out", "w", stdout);
}

int main()
{
    // fileIO();
    n = read();
    for (int i = 1; i <= n; i++)
        hi[i] = read();
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        hi[i] = max(hi[i], 0);
        int regret3 = min(hi[i] / 3, ai[i]);
        hi[i] -= regret3 * 3;
        int regret2 = hi[i] >> 1;
        hi[i] -= regret2 * 2;
        int regret1 = hi[i];
        hi[i] = 0, ans += regret1 + regret2 + regret3;
        ai[i + 1] += regret3 * 2 + regret2;
        hi[i + 1] -= regret2 + regret1 * 2;
    }
    printf("%lld\n", ans);
    return 0;
}

B – 手链强化

终于碰到了 Burnside 和 Polya 的题了。

首先这里的置换操作只有一个旋转，所以循环节是 \(\gcd\)，所以我们只需要来算 \(\gcd\) 个等价类时的方案数。

其实等价类方案数也很好求，设 \(f[i][0], f[i][1]\) 为考虑过 \(i\) 个等价类、位置上有没有染色的方案数，直接 \(f[i][0] = f[i – 1][1] + f[i – 1][0], f[i][1] = k f[i – 1][0]\)，并且发现这个矩阵快速幂也很好做。

还要注意一点，就是开头的等价类和末尾的等价类不能相邻，所以分类考虑出方案数为 \(f[t – 1][0] + f[t – 1][1] + f[t – 2][0]\)。

最后答案就是：

\[ \frac{1}{n} \sum_{d|n} (f[d – 1][0] + f[d – 1][1] + f[d – 2][0]) \varphi(\frac{n}{d}) \]

@@ -0,0 +1,103 @@
// bracelet.cpp
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int n, kind, dp[1010][2][2];

void fileIO()
{
    freopen("bracelet.in", "r", stdin);
    freopen("bracelet.out", "w", stdout);
}

struct matrix
{
    int mat[2][2];
    int *operator[](const int &idx) { return mat[idx]; }
    void clear() { memset(mat, 0, sizeof(mat)); }
    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        ret.clear();
        for (int i = 0; i < 2; i++)
            for (int k = 0; k < 2; k++)
                if (mat[i][k])
                    for (int j = 0; j < 2; j++)
                        if (rhs.mat[k][j])
                            ret[i][j] = (0LL + ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }
    matrix operator^(const int &idx)
    {
        int tim = idx;
        matrix ret, bas = *this;
        ret.clear(), ret[0][0] = ret[1][1] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} trans, init;

matrix getFn(int x) { return init * (trans ^ x); }

int phi(int x)
{
    int ret = x;
    for (int i = 2; 1LL * i * i <= x; i++)
        if (x % i == 0)
        {
            ret -= ret / i;
            while (x % i == 0)
                x /= i;
        }
    if (x != 1)
        ret -= ret / x;
    return ret % mod;
}

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int inv2 = fpow(2, mod - 2);

int solve(int x)
{
    if (x == 1)
        return phi(n / x);
    matrix c = getFn(x - 2);
    int pans = 1LL * kind * c[0][0] % mod;
    c = c * trans;
    pans = (0LL + pans + c[0][0] + c[0][1]) % mod;
    pans = 1LL * pans * phi(n / x) % mod;
    return pans;
}

int main()
{
    // fileIO();
    scanf("%d%d", &n, &kind), init[0][0] = 1, trans[0][0] = trans[1][0] = 1, trans[0][1] = kind;
    int ans = 0;
    for (int i = 1; 1LL * i * i <= n; i++)
        if (n % i == 0)
            ans = (0LL + ans + solve(i) + ((1LL * i * i == n) ? 0 : solve(n / i))) % mod;
    printf("%lld\n", 1LL * ans * fpow(n, mod - 2) % mod);
    return 0;
}

C – 数字收藏

不难，发现贡献是莫比乌斯函数乘上已有倍数个数，所以写完了。

@@ -0,0 +1,104 @@
// number.cpp
#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

typedef long long ll;

int n, d, mu[MAX_N], primes[MAX_N], tot, psiz[MAX_N];
bool vis[MAX_N];
multiset<int> pos;
ll ans;

void fileIO()
{
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
}

inline char nc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

int main()
{
    // fileIO();
    n = read(), d = read();
    mu[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (!vis[i])
            primes[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && 1LL * i * primes[j] < MAX_N; j++)
        {
            vis[i * primes[j]] = true, mu[i * primes[j]] = -mu[i];
            if (i % primes[j] == 0)
            {
                mu[i * primes[j]] = 0;
                break;
            }
        }
    }
    // printf("%.6lf\n", 1.0 * clock() / CLOCKS_PER_SEC);
    // answer the queries;
    while (n--)
    {
        int opt = read(), x = read();
        if (x % d != 0)
        {
            printf("%lld\n", ans);
            continue;
        }
        x /= d;
        if (opt == 1)
        {
            pos.insert(x);
            for (int i = 1; 1LL * i * i <= x; i++)
                if (x % i == 0)
                {
                    ans += mu[i] * psiz[i], psiz[i]++;
                    if (x / i != i)
                        ans += mu[x / i] * psiz[x / i], psiz[x / i]++;
                }
        }
        else
        {
            if (pos.find(x) == pos.end())
            {
                printf("%lld\n", ans);
                continue;
            }
            pos.erase(pos.find(x));
            for (int i = 1; 1LL * i * i <= x; i++)
                if (x % i == 0)
                {
                    psiz[i]--, ans -= mu[i] * psiz[i];
                    if (x / i != i)
                        psiz[x / i]--, ans -= mu[x / i] * psiz[x / i];
                }
        }
        printf("%lld\n", ans);
    }
    // printf("%.6lf\n", 1.0 * clock() / CLOCKS_PER_SEC);
    return 0;
}