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;
}