「FZOI」OI 周赛 #4 Div.1 – 题解

A - 对称的多边形

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

typedef long long ll;

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, xi[MAX_N], yi[MAX_N], len[MAX_N];
ll seq[MAX_N];

ll getDist(int x1, int y1, int x2, int y2)
{
    return ll(x1 - x2) * ll(x1 - x2) + ll(y1 - y2) * ll(y1 - y2);
}

ll getAngle(int orgx, int orgy, int x1, int y1, int x2, int y2)
{
    ll dx1 = x1 - orgx, dy1 = y1 - orgy;
    ll dx2 = x2 - orgx, dy2 = y2 - orgy;
    return dx1 * dy2 - dx2 * dy1;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(len, 0, sizeof(len));
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &xi[i], &yi[i]);
        // create new string for manacher;
        for (int i = 0; i < n; i++)
        {
            seq[(i << 1) | 1] = getDist(xi[i], yi[i], xi[(i + 1) % n], yi[(i + 1) % n]);
            seq[(i << 1)] = getAngle(xi[i], yi[i], xi[(i + n - 1) % n], yi[(i + n - 1) % n], xi[(i + 1) % n], yi[(i + 1) % n]);
        }
        int tot_len = n << 1;
        for (int i = 0; i < n; i++)
            seq[i + tot_len] = seq[i];
        tot_len <<= 1;
        int R = 0, ans = 0, mid = 0;
        for (int i = 0; i < tot_len; i++)
        {
            if (i < R)
                len[i] = min(R - i, len[mid * 2 - i]);
            else
                len[i] = 1;
            while (i - len[i] >= 0 && i + len[i] < tot_len && seq[i + len[i]] == seq[i - len[i]])
                len[i]++;
            if (i + len[i] > R)
                R = i + len[i], mid = i;
            if (len[i] >= n + 1)
                ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B - 最小方差树

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 2020;

int fa[MAX_N], n, m;
double ans = (double)(0x3f3f3f3f);

struct edge
{
    int from, to, weight;
    double cmp;
    bool operator<(const edge &d) const { return cmp < d.cmp; }
} edges[MAX_N];

int find(int x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }

void kruskal(double avg)
{
    double sqr = 0;
    double len = 0;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        edges[i].cmp = 1.0 * (avg - 1.0 * edges[i].weight) * (avg - 1.0 * edges[i].weight);
    sort(edges + 1, edges + 1 + m);
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= m; i++)
    {
        int x = edges[i].from, y = edges[i].to;
        if (find(x) != find(y))
            fa[fa[x]] = fa[y], cnt++, len += edges[i].weight, q.push(i);
    }
    len /= (n - 1);
    while (!q.empty())
    {
        int u = q.front();
        sqr += (edges[u].weight - len) * (edges[u].weight - len);
        q.pop();
    }
    if (cnt == n - 1)
        ans = min(ans, sqrt(sqr / (n - 1)));
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].weight);
    for (double avg = 0.25; avg <= 100; avg += 0.25)
        kruskal(avg);
    printf("%.4lf", ans);
    return 0;
}

C - 数列计数

为啥你们都写得那么复杂？其实发现容斥+DP就可以比较轻松的做出来了。我们发现先算和为$p$的倍数的任意方案数，然后再减去只用质数的方案数就是答案。

第一部分

第一部分的式子并不难，设置$dp[i][j]$为前$i$个数的和在模意义下为$j$的方案数，那么转移如下：
$$
dp[i][j] = \sum_{k = 0}^{p - 1} dp[i - 1][(j - k) \bmod p] \times c_k
$$
其中$c_k$就是在$m$的值域内选模意义下为$k$的方案数。根据题意，$c_k$也比较显然：
$$
ck = \begin{cases} \lfloor \frac{m}{p} \rfloor, k = 0 \ \lfloor \frac{m - k}{p} \rfloor + 1, k < m \ 1, k = m \ 0, k > m \end{cases}
$$
因为序列长度很长，那么我们可以考虑构建矩阵来优化之：
$$
dp'[0][j] = \sum{k = 0}^{p - 1} dp[0][j - k \bmod p] \times ck \ dp'[0][j] = \sum{k = 0}^{p - 1} dp[0][k] \times c{(j - k \bmod p)}
$$
再参考矩阵乘法的意义：
$$
A[i][j] = \sum{k = 0}^{p - 1} B[i][k] \times C[k][j]
$$
那么我们的矩阵其实就很好构造：
$$
trans[k][j] = c_{(j - k \bmod p)}
$$

第二部分

第二部分差不多，我们需要线性筛把$m$内的质数筛出来，然后在桶里计数：$bucket[i \bmod p]++$。之后在$trans$矩阵内减去这些质数的方案数，做一遍即可。

代码

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

using namespace std;

const int MAX_N = 110, MAX_M = 2e7 + 200, mod = 20170408;

int primes[MAX_M], tot, n, m, p, table[MAX_N];
bool vis[MAX_M];

struct matrix
{
    int mat[MAX_N][MAX_N];

    matrix() { memset(mat, 0, sizeof(mat)); }

    int *operator[](const int &rhs) { return mat[rhs]; }

    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        for (int i = 0; i < p; i++)
            for (int j = 0; j < p; j++)
                for (int k = 0; k < p; k++)
                    ret[i][j] = (1LL * ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }

    matrix operator^(const int &rhs)
    {
        int tim = rhs;
        matrix ret, bas = *this;
        for (int i = 0; i < p; i++)
            ret[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} dp, trans;

void sieve()
{
    for (int i = 2; i <= m; i++)
    {
        if (!vis[i])
            primes[++tot] = i;
        for (int j = 1; j <= tot && 1LL * i * primes[j] <= m; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= tot; i++)
        table[primes[i] % p]++;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    sieve();
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] %= mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    int ans = dp[0][0];
    memset(dp.mat, 0, sizeof(dp.mat));
    memset(trans.mat, 0, sizeof(trans.mat));
    for (int c = 0; c < p; c++)
        for (int b = 0; b < p; b++)
        {
            int delta = (c - b + p) % p;
            if (delta == 0)
                trans[b][c] = m / p;
            else if (delta < m)
                trans[b][c] = int((m - delta) / p) + 1;
            else if (delta == m)
                trans[b][c] = 1;
            else
                trans[b][c] = 0;
            trans[b][c] = (trans[b][c] + mod - table[delta]) % mod;
        }
    dp[0][0] = 1, dp = dp * (trans ^ n);
    ans = (ans + mod - dp[0][0]) % mod;
    printf("%d\n", ans);
    return 0;
}