A. 天地一抹红
同行的转移是 \(kx + b\) 的形式，可以李超树维护
其实可以斜率优化，但是懒得动脑子
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, ll> pil;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxm = 2e4 + 55, maxn = 105;
ll calc(pil line, int x){return 1ll * line.first * x + line.second;}
int w[maxn][maxm], h[maxn][maxm], a[maxn][maxm];
int n, m, F;
struct seg{
pil t[maxm << 2 | 1];
void build(int x, int l, int r){
t[x] = {0, -1e18};
if(l == r)return;
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
void modify(int x, int l, int r, pil line){
int mid = (l + r) >> 1;
if(calc(t[x], mid) < calc(line, mid))swap(t[x], line);
if(l == r)return;
if(calc(t[x], l) < calc(line, l))modify(x << 1, l, mid, line);
if(calc(t[x], r) < calc(line, r))modify(x << 1 | 1, mid + 1, r, line);
}
ll query(int x, int l, int r, int v){
ll ans = calc(t[x], v);
if(l == r)return ans;
int mid = (l + r) >> 1;
if(v <= mid)return max(ans, query(x << 1, l, mid, v));
else return max(ans, query(x << 1 | 1, mid + 1, r, v));
}
}T;
ll f[maxn][maxm];
int main(){
freopen("red.in","r",stdin);
freopen("red.out","w",stdout);
n = read(), m = read(), F = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
w[i][j] = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
h[i][j] = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
a[i][j] = read();
for(int i = 1; i <= n; ++i){
T.build(1, 1, m); ll mx = -1e18;
for(int j = 1; j <= m; ++j){
if(i == 1 && j == 1)f[i][j] = F;
else f[i][j] = max(f[i - 1][j] - w[i - 1][j], T.query(1, 1, m, a[i][j]));
mx = max(f[i][j] - w[i][j], mx);
T.modify(1, 1, m, pil(h[i][j], mx));
}
}
printf("%lld\n", max(-1ll, f[n][m]));
return 0;
}
B. 最简根式
不难发现是求 \(\sum_{a = 1}^n\sum_{b = 1}^{n}[\gcd(a, b) 含平方因子]\)
枚举 \(gcd\) 的平方因子，简单容斥得到答案为
\(-\sum_{i = 2}^{\sqrt n} \mu(i)(\lfloor\frac{n}{i^2}\rfloor)^2\)
对 \(\lfloor\frac{n}{i^2}\rfloor\) 整除分块
预处理一部分，杜教筛一部分，复杂度是对的
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, ll> pil;
ll read() {
ll x = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
do {
x = x * 10 + (c ^ 48);
c = getchar();
} while (isdigit(c));
return x;
}
const int mod = 998244353;
const int maxn = 6e7 + 5;
int prime[maxn], cnt, mu[maxn];
bool flag[maxn];
void init(int n) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!flag[i])
prime[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && prime[j] * i <= n; ++j) {
flag[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 2; i <= n; ++i) mu[i] += mu[i - 1];
}
unordered_map<ll, int> mp;
int calc(ll n) {
if (n <= 6e7)
return mu[n];
if (mp.count(n))
return mp[n];
ll ans = 1;
for (ll l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = (ans - 1ll * (r - l + 1) % mod * calc(n / l)) % mod;
}
ans = (ans + mod) % mod;
return mp[n] = ans;
}
void solve() {
ll n = read(), ans = 0;
for (ll l = 2, r; l * l <= n; l = r + 1) {
r = sqrt(n / (n / (l * l)));
ans = (ans +
1ll * ((n / (l * l)) % mod) * ((n / (l * l)) % mod) % mod * (calc(r) - calc(l - 1)) % mod) %
mod;
}
printf("%lld\n", ((mod - ans) % mod + mod) % mod);
}
int main() {
freopen("math.in", "r", stdin);
freopen("math.out", "w", stdout);
init(6e7);
int t = read();
for (int i = 1; i <= t; ++i) solve();
return 0;
}
C. 图床
\(hash\) 找出出现的字符串个数 \(k\)
\[ P(n) = \frac{\binom{n}{k}(k^m - (k - 1)^m)}{n^m} \]找到最接近的 \(n\)
这是个单峰函数
又有 \(P(n) < P(n + 1) <=> (n + 1 - k)(n + 1)^m < (n + 1)n^m\)
可以直接二分
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int mod = 2140207;
int read() {
int x = 0;
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
do {
x = (x * 29ll + (c - 'a' + 1)) % mod;
c = getchar();
} while (c >= 'a' && c <= 'z');
return x;
}
int ln, rn, m;
bitset<mod> rem;
void solve() {
int k = 0;
for (int i = 1; i <= m; ++i) {
int tmp = read();
if (!rem[tmp])
rem[tmp] = true, ++k;
}
int l = max(ln, k), r = rn;
while (l < r) {
int mid = (l + r) >> 1;
if (log2(mid - k + 1) + log2(mid + 1) * m < log2(mid + 1) + log2(mid) * m)
l = mid + 1;
else
r = mid;
}
rem.reset();
printf("%d\n", l);
}
int main() {
freopen("pic.in", "r", stdin);
freopen("pic.out", "w", stdout);
int T;
double a, b, c, d;
scanf("%d%lf%lf%lf%lf%d%d%d", &T, &a, &b, &c, &d, &ln, &rn, &m);
for (int i = 1; i <= T; ++i) solve();
return 0;
}