abc227 Question

There is no state on the examination room.


A

Come with periodicity.


B

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