# abc227 Question

There is no state on the examination room.

#### A

Come with periodicity.

Enumeration.

#### C

Discover$$A\le \sqrt[3] N$$,$$B \le \sqrt N$$Directly enumerated and found that you can run. The complexity will not be certified, it seems to use the calcination.
I don’t know what I want, enumerate$$B$$Use the entire division. . . The complexity is the same, but the constant is t.

#### D

A natural idea isConsider the process of choice deletionDiscover the priority of the current largest$$k$$A certain best, but time complexity fly.
There is another common TRICK is: We don’t consider the process of choice, but consider how much contribution to the answer. Found nowhere to choose$$t$$Group out,$$a_i$$The contribution of the provided theory is the most$$\min(t,a_i)$$, we have two points each time$$t$$

#### E

Don’t throw it easily

Obviously directly simulate this switching process is not. Consider a sequence will only exchange$$n$$
That can be naturally introduced to this DP status: DP [Teachment 1 Number] [There are several K] [there are several E] [There are several Y] [exchanged G times] can construct the last Number of rows of numbers. There is actually a very common trick —- direct constructive answer sequence. at mePrevious blog
Then think about it carefully and find that you can forward (ie, interchangeably). Then just push it.
(I won’t be played like this.

#### F

The first feel is DP. Discover this$$k$$Big (and also required) is not well maintained.
trick: We consider setting a threshold$$p$$, ie$$k$$Large numbers, if the current number is more than equal$$p$$Just add his contribution. How to ensure that this number must be$$k$$
Reply: Is it better than him?$$k-1$$? Hahahaha SB, if this path has not been valued$$p$$The number, then you will find this path only$$k-1$$And if the same number is much, these may be added more.
Solution: For the current value equal to the threshold$$p$$Time, special treatment: You can choose or don’t choose.
So we run a DP for each number, time complexity:$$\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

Definition$$a\sim b=a\times(a+1)\times (a+2)…\times b$$.
$$k$$Small. So we can put the final format as$$\frac {(n+k-1)\sim n}{1\sim k}$$.
With intuition, we naturally think of classification discussions (root sections) according to the unique decomposition theorem (ie, the number is equal to the index).

1. $$p>\max(k,\sqrt n)$$($$p$$​​Troubon. Such$$p$$Only the molecule will be removed once, and the denominator will not be completely removed. So we should consider how to remove it.$$\le k$$The quality contem.
2. $$p\le\max(k,\sqrt n)$$($$p$$As the number). Such$$p$$$$n/\ln(n)$$First of all, for each prime number$$log_p$$The method finds that the number in the interval will take its index. Consider the method of sieve, will$$[n-k+1,n]$$$$<p$$All parties are all about, complexity$$<\mathcal {O}(klog)$$. Remaining$$p>k$$The factor, then this question is done, nor is it difficult, considering the basic skills of the sieve quality.
#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;
}


• Top