A – Function

在考场上只推出来 \(f(x) = \mu(x) * \sigma_0^2(x) = \prod_{i = 1}^m (2c_i + 1)\)，显然用 min_25 就可以直接秒杀（但是我忘了板子呜呜呜呜呜）

其实我们都推理到这一步了，发现无非就是把 \(c_i\) 乘了个 \(2\)。所以其实 \(f(x) = \sigma_0(x^2)\)。这个其实推出了上面的那个 Dirichlet 卷积就已经清楚很多了。

现在考虑如何用快速的方法筛出 \(\sum_{x = 1}^n \sigma_0(x^2)\)。用 SPOJ DIVCNT2 的方法筛即可。

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

using namespace std;

const int MAX_N = 1e6 + 500;

typedef long long ll;

int T, n, primes[MAX_N], tot;
ll sigma[MAX_N], mu[MAX_N], pmu[MAX_N];
bool vis[MAX_N];
unordered_map<ll, ll> ump;

ll getSigma(ll upper)
{
    if (upper < MAX_N)
        return sigma[upper];
    ll ret = 0;
    for (ll i = 1, gx; i <= upper; i = gx + 1)
    {
        gx = upper / (upper / i);
        ret += 1LL * (upper / i) * (gx - i + 1);
    }
    return ret;
}

ll getMu2(ll upper)
{
    if (upper < MAX_N)
        return pmu[upper];
    ll ret = 0;
    for (int i = 1; 1LL * i * i <= upper; i++)
        ret += 1LL * mu[i] * (upper / (1LL * i * i));
    return ret;
}

int main()
{
    sigma[1] = mu[1] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (!vis[i])
            primes[++tot] = i, mu[i] = -1, sigma[i] = 2;
        for (int j = 1; j <= tot && 1LL * i * primes[j] < MAX_N; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                mu[i * primes[j]] = 0;
                sigma[i * primes[j]] = 2LL * sigma[i] - sigma[i / primes[j]];
            }
            else
            {
                mu[i * primes[j]] = -mu[i];
                sigma[i * primes[j]] = sigma[i] * sigma[primes[j]];
            }
        }
    }
    for (int i = 1; i < MAX_N; i++)
        pmu[i] = pmu[i - 1] + mu[i] * mu[i], sigma[i] += sigma[i - 1];
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        ll ret = 0;
        for (int i = 1, gx; i <= n; i = gx + 1)
        {
            gx = n / (n / i);
            ret += getSigma(n / i) * (getMu2(gx) - getMu2(i - 1));
        }
        printf("%lld\n", ret);
    }
    return 0;
}

B – Permutation

打表发现，如果没确定的位置，答案就是 \(1 \times 3 \times 5 \dots\)。如果确定了，那就是 \(n!\)。

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

using namespace std;

const int MAX_N = 1e5 + 200, mod = 998244353;

int n, ai[MAX_N], deg[MAX_N];
bool vis[MAX_N];

bool dfs(int u)
{
    if (vis[u])
        return false;
    vis[u] = true;
    return ai[u] ? !dfs(ai[u]) : 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ai[i]);
        if (ai[i] != 0)
            deg[ai[i]] = 1;
    }
    if (n & 1)
        puts("0"), exit(0);
    int x = 0, y = 0;
    for (int i = 1, tmp; i <= n; i++)
        if (!deg[i])
            tmp = dfs(i), y += tmp, x += !tmp;
    for (int i = 1; i <= n; i++)
        if (!vis[i] && dfs(i))
            puts("0"), exit(0);
    int ans = 1;
    for (int i = 1; i <= x; i += 2)
        ans = 1LL * ans * i % mod;
    ans = 1LL * ans * ans % mod;
    for (int i = x + 1; i <= x + y; i++)
        ans = 1LL * ans * i % mod;
    printf("%d\n", ans);
    return 0;
}

C – Subsequence

子序列自动上跑一个 DP，设计状态的时候要利用答案应该不大的性质：设 \(dp[i][j]\) 表示答案长度为 \(i\) 且到了 A 串自动机节点上 \(j\) 的最大的 B 串自动机节点。如果有 \(dp[i][a + 1] = b + 1\) （失配），那么答案就是 \(i\)。

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

using namespace std;

const int MAX_N = 4040;

int n, m, k, nxt[2][MAX_N][MAX_N], sA[MAX_N], sB[MAX_N], dp[MAX_N][MAX_N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &sA[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &sB[i]);
    for (int c = 1; c <= k; c++)
        nxt[0][n][c] = n + 1, nxt[1][m][c] = m + 1, nxt[0][n + 1][c] = n + 1, nxt[1][m + 1][c] = m + 1;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int c = 1; c <= k; c++)
            nxt[0][i][c] = nxt[0][i + 1][c];
        nxt[0][i][sA[i + 1]] = i + 1;
    }
    for (int i = m - 1; i >= 0; i--)
    {
        for (int c = 1; c <= k; c++)
            nxt[1][i][c] = nxt[1][i + 1][c];
        nxt[1][i][sB[i + 1]] = i + 1;
    }
    memset(dp, -1, sizeof(dp)), dp[0][0] = 0;
    for (int i = 0; i <= min(n, m); i++)
    {
        for (int j = 0; j <= n; j++)
            if (dp[i][j] != -1)
            {
                for (int c = 1; c <= k; c++)
                    dp[i + 1][nxt[0][j][c]] = max(dp[i + 1][nxt[0][j][c]], nxt[1][dp[i][j]][c]);
            }
        if (dp[i + 1][n + 1] == m + 1)
            printf("%d\n", i + 1), exit(0);
    }
    return 0;
}