A – Cow Gymnasts

规律题。只要能发现合法序列的极差不超过 $1$ 这个性质就可以算了。直接：

$$ans = 2 – n + \sum_{i = 1}^{n – 1} 2^{\gcd(i, n)}$$

然后这个显然可以用某些 Polya 题的方式用数论函数进行优化，就没了。

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

using namespace std;

const int MAX_N = 1e5 + 200, mod = 1e9 + 7;

typedef long long ll;

ll n, acc, ans;
vector<pair<ll, int>> nset;

void fileIO(string src)
{
    freopen((src + ".in").c_str(), "r", stdin);
    freopen((src + ".out").c_str(), "w", stdout);
}

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

void dfs(int pos, ll gcd, ll phiup, ll phidown)
{
    if (pos == int(nset.size()))
    {
        if (gcd == 1)
            return;
        ans += fpow(2, (n / gcd) % (mod - 1)) * ((1LL * gcd / phidown % mod * phiup % mod) % mod) % mod;
        ans %= mod;
        return;
    }
    dfs(pos + 1, gcd, phiup, phidown);
    phiup = 1LL * phiup * (nset[pos].first - 1) % mod;
    phidown = 1LL * phidown * nset[pos].first;
    for (int i = 1; i <= nset[pos].second; i++)
    {
        gcd *= nset[pos].first;
        dfs(pos + 1, gcd, phiup, phidown);
    }
}

int main()
{
    // fileIO("gymnasts");
    scanf("%lld", &n), acc = n;
    for (ll i = 2; 1LL * i * i <= acc; i++)
        if (acc % i == 0)
        {
            int cnt = 0;
            while (acc % i == 0)
                cnt++, acc /= i;
            nset.push_back(make_pair(i, cnt));
        }
    if (acc > 1)
        nset.push_back(make_pair(acc, 1));
    dfs(0, 1, 1, 1);
    printf("%lld\n", (2LL + ans - (n % mod) + mod) % mod);
    return 0;
}

B – Cow Date

这个题比较有意思。我们考虑化简式子：

$$f_{l, r} = \prod_{i = l}^r (1 – p_i) \sum_{i = l}^r \frac{p_i}{1 – p_i}$$

假设是从 $[l, r – 1]$ 处转移而来，那么：

$$\begin{aligned} f_{l, r} &= (1 – p_r) \prod_{i = l}^{r – 1} (1 – p_i) (\frac{p_r}{1 – p_r} + \sum_{i = l}^{r – 1} \frac{p_i}{1 – p_i}) \\ &= (1 – p_r) \prod_{i = l}^{r – 1} (1 – p_i) \sum_{i = l}^{r – 1} \frac{p_i}{1 – p_i} + p_r \prod_{i = l}^{r – 1} (1 – p_i) \\ &= (1 – p_r) f_{l, r – 1} + p_r \prod_{i = l}^{r – 1} (1 – p_i) \end{aligned}$$

显然可以考虑 Two-Pointers，然后考虑多出来的那一坨是否会使得答案更优即可。

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

using namespace std;

const int MAX_N = 1000000 + 200;

typedef long double ld;

int n, pi[MAX_N], ans;

void fileIO(string src)
{
    freopen((src + ".in").c_str(), "r", stdin);
    freopen((src + ".out").c_str(), "w", stdout);
}

int main()
{
    // fileIO("cowdate");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &pi[i]), ans = max(ans, pi[i]);
    if (ans >= 5e5)
        printf("%d\n", ans), exit(0);
    int rptr = 1;
    ld acc = pi[1], prod = 1000000 - pi[1];
    while (rptr < n && prod > acc)
    {
        rptr++, acc = acc * (1000000 - pi[rptr]) / 1000000 + pi[rptr] * prod / 1000000;
        prod = prod * (1000000 - pi[rptr]) / 1000000;
    }
    ans = max(ans, int(acc));
    for (int lptr = 2; lptr <= n; lptr++)
    {
        prod = prod * 1000000 / (1000000 - pi[lptr - 1]);
        acc = (acc * 1000000 - pi[lptr - 1] * prod) / (1000000 - pi[lptr - 1]);
        while (rptr < n && prod > acc)
        {
            rptr++, acc = acc * (1000000 - pi[rptr]) / 1000000 + pi[rptr] * prod / 1000000;
            prod = prod * (1000000 - pi[rptr]) / 1000000;
        }
        ans = max(ans, int(acc));
    }
    printf("%d\n", ans);
    return 0;
}

C – Moorio Kart

妈的，这题 $\Theta(n^3)$ 在考场上送了（写得太复杂了我真的是sb）。

首先，众所周知，这道题需要你把一堆树串起来，然后计算所有的、大于 $y$ 的环长。正常来讲这个 $\Theta(n^3)$ 的背包可以做，然后搞一个圆排列数即可。

复杂度还是太大了。然而，如果你做背包的时候做一个小剪枝，那么复杂度就会降低到 $\Theta(n^2 \sqrt n)$ 的级别。考虑合并，每个块内的路径个数为 $\Theta(k^2)$、背包大小为 $Y – Xk$。这两个东西乘起来最糟糕的情况就是 $\Theta(n^2 \sqrt n)$ 的级别。

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

using namespace std;

const int MAX_N = 1.5e3 + 200, mod = 1e9 + 7;

typedef long long ll;

int n, m, X, Y, head[MAX_N], current, dist[MAX_N][MAX_N], idx[MAX_N], mem[MAX_N];
int coltot, ans, prod[MAX_N][2600], tot[MAX_N][2600], F[2600][2], tmp[2600][2];

void fileIO(string src)
{
    freopen((src + ".in").c_str(), "r", stdin);
    freopen((src + ".out").c_str(), "w", stdout);
}

struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

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

void dfs(int u, int fa, int org, int dep)
{
    if (fa)
    {
        prod[idx[u]][min(dep, Y)] = (0LL + prod[idx[u]][min(dep, Y)] + dep) % mod;
        tot[idx[u]][min(dep, Y)]++;
    }
    dist[org][u] = dep;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u, org, dep + edges[i].weight);
}

int main()
{
    // fileIO("mooriokart");
    memset(head, -1, sizeof(head)), memset(dist, -1, sizeof(dist));
    scanf("%d%d%d%d", &n, &m, &X, &Y);
    for (int i = 1; i <= n; i++)
        mem[i] = i;
    for (int i = 1, u, v, w; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
        if (find(u) != find(v))
            mem[find(u)] = find(v);
    }
    for (int i = 1; i <= n; i++)
    {
        if (idx[find(i)] == 0)
            idx[find(i)] = ++coltot;
        idx[i] = idx[find(i)];
    }
    for (int i = 1; i <= n; i++)
        dfs(i, 0, i, 0);
    int base = min(Y, coltot * X);
    F[base][0] = 1, F[base][1] = coltot * X;
    for (int i = 1; i <= coltot; i++)
    {
        for (int j = base; j <= Y; j++)
            tmp[j][0] = tmp[j][1] = 0;
        for (int j = 0; j <= Y; j++)
            if (tot[i][j])
                for (int k = base; k <= Y; k++)
                    if (F[k][0])
                    {
                        tmp[min(j + k, Y)][0] = (0LL + tmp[min(j + k, Y)][0] + 1LL * tot[i][j] * F[k][0] % mod) % mod;
                        tmp[min(j + k, Y)][1] = (0LL + tmp[min(j + k, Y)][1] + 1LL * prod[i][j] * F[k][0] % mod + 1LL * F[k][1] * tot[i][j] % mod) % mod;
                    }
        memcpy(F, tmp, sizeof(tmp));
    }
    ans = F[Y][1];
    for (int i = 1; i < coltot; i++)
        ans = 1LL * ans * i % mod;
    printf("%lld\n", 1LL * ans * ((mod + 1) >> 1) % mod);
    return 0;
}