考场上没状态啊
A
用周期性算即可。
B
枚举。
C
发现 \(A\le \sqrt[3] N\)，\(B \le \sqrt N\)，直接枚举，发现能跑过。复杂度不会证，好像要用微积分。
我考场不知道在想什么，枚举 \(B\) 的时候用的整除分块。。。复杂度是一样的，但常数大T了。
D
一个很自然的想法是 考虑选数删除的过程，发现优先选当前最大的 \(k\) 个一定最优，但时间复杂度飞了。
又有一个很常见的 trick 是：我们不考虑选数的过程，而是考虑每个会对答案产生多少贡献。发现如果最后要选 \(t\) 组出来，\(a_i\) 提供的贡献理论上最大是 \(\min(t,a_i)\)，而我们每次二分这个 \(t\) 即可。
E
想法不要轻易扔了
显然直接模拟这个交换过程是不行的。考虑要得到一种序列最多只会交换 \(n\) 次。
那便可以很自然的引出这样一个dp状态：dp[构造出前i个数][有几个K][有几个E][有几个Y][交换了g次]能构造出最后的数列的方案数。这里其实有个很常见的 trick 吧————直接构造答案序列。在我 之前的博客 中有讲。
然后仔细想一想，发现可以贪心地转移（即尽量互换）。然后随便推推就行了。（我这样写题解会不会被打）
F
第一感觉是 dp。发现这个第 \(k\) 大（而且还要求和）不好动态维护。
trick：我们考虑设置一个阈值 \(p\)，即第 \(k\) 大的数字，如果当前数大于等于 \(p\)，就加上他的贡献。那如何保证这个数一定是第 \(k\) 大？
Reply：不就是比他大的有 \(k-1\) 个吗？哈哈哈哈sb，如果这条路径没经过值等于 \(p\) 的数，那你会发现这条路径只加了 \(k-1\) 个。而且如果相同的数很多，可能多加了这些相同的数。
解决办法：对于当前值等于阈值 \(p\) 的时候，特殊处理：可以使其选或不选。
所以对于每个数我们跑个 dp，时间复杂度：\(\mathcal {O}(H^2W^2k)\)。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 35;
const LL lof = 4e18;
int n, m, k, a[MAXN][MAXN];
LL ans = lof, dp[MAXN][MAXN][MAXN << 1];
LL Calc(int x, int y) {
for(int i = 1; i <= max(n, m); i ++) for(int j = 0; j <= k; j ++) dp[i][0][j] = dp[0][i][j] = lof;
dp[0][1][0] = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
if(a[i][j] == a[x][y]) {
for(int u = 0; u <= k; u ++) {
dp[i][j][u] = lof;
if(u) dp[i][j][u] = min(dp[i - 1][j][u - 1], dp[i][j - 1][u - 1]) + a[i][j];
dp[i][j][u] = min(dp[i][j][u], min(dp[i - 1][j][u], dp[i][j - 1][u]));
if(dp[i][j][u] > lof) dp[i][j][u] = lof;
}
}
else if(a[i][j] > a[x][y]) {
dp[i][j][0] = lof;
for(int u = 1; u <= k; u ++) {
dp[i][j][u] = min(dp[i - 1][j][u - 1], dp[i][j - 1][u - 1]) + (a[i][j] >= a[x][y] ? a[i][j] : 0);
if(dp[i][j][u] > lof) dp[i][j][u] = lof;
}
}
else {
for(int u = 0; u <= k; u ++) {
dp[i][j][u] = min(dp[i - 1][j][u], dp[i][j - 1][u]) + (a[i][j] >= a[x][y] ? a[i][j] : 0);
if(dp[i][j][u] > lof) dp[i][j][u] = lof;
}
}
// for(int u = 0; u <= k; u ++) printf("%d %d %d %lld\n", i, j, u, dp[i][j][u]);
}
}
// printf("|%d %d %d %lld|\n", x, y, k, dp[n][m][k]);
return dp[n][m][k];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) ans = min(ans, Calc(i, j));
printf("%lld", ans);
return 0;
}
G
定义 \(a\sim b=a\times(a+1)\times (a+2)...\times b\)。
\(k\) 很小。所以我们可以把最后的式子化为 \(\frac {(n+k-1)\sim n}{1\sim k}\)。
凭借直觉，根据唯一分解定理（即因数个数等于指数相加再连乘），我们自然想到分类讨论（根号分治）。
- \(p>\max(k,\sqrt n)\)（\(p\) 为质数）。这样的 \(p\) 只会整除分子一次，不会整除分母。所以我们应该考虑怎么消掉 \(\le k\) 的质因子。
- \(p\le\max(k,\sqrt n)\)（\(p\) 为质数）。这样的 \(p\) 约有 \(n/\ln(n)\) 个。首先对于每个质数可以用 \(log_p\) 的方法求出区间内的数乘起来它的指数。考虑用埃筛的方法，将 \([n-k+1,n]\) 中的数中 \(<p\) 地因子全部约掉，复杂度 \(<\mathcal {O}(klog)\)。剩下的就是 \(p>k\) 的因子了，然后这道题就做完了，也不是很难，考虑筛质数的基本功。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
using namespace std;
const int Mod = 998244353, MAXK = 1e6 + 5;
LL n, a[MAXK], ans = 1;
int k, pr[MAXK], tot, N;
bool vis[MAXK];
void Prime() {
for(int i = 2; i <= N; i ++) {
if(!vis[i]) pr[++ tot] = i;
for(int j = 1; j <= tot && i * pr[j] <= N; j ++) {
vis[i * pr[j]] = 1;
if(i % pr[j] == 0) break;
}
}
}
LL Calc(int p, LL l, LL r) {
LL res = 0;
for(LL i = p; i <= r; i *= p) {
res += r / i - (l - 1) / i;
}
return res;
}
int main() {
scanf("%lld%d", &n, &k);
N = max((int)sqrt(n) + 1, k);
Prime();
for(int i = 1; i <= k; i ++) a[i] = n - k + i;
for(int i = 1; i <= tot; i ++) {
LL t = Calc(pr[i], n - k + 1, n) - Calc(pr[i], 1LL, (LL)k);
ans = (ans * ((t + 1) % Mod)) % Mod;
}
for(int i = 1; i <= tot; i ++) {
for(LL j = (n - k + 1) / pr[i] * pr[i]; j <= n; j += pr[i]) {
if(j < n - k + 1) continue;
while(a[j - n + k] % pr[i] == 0) a[j - n + k] /= pr[i];
}
}
for(int i = 1; i <= k; i ++) {
if(a[i] > 1) ans = ans * 2 % Mod;
}
printf("%lld", ans);
return 0;
}