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