T1. number off

You can first find out all numbers with \ (7 \) in the lower digit of the decimal representation, and then enumerate the multiples of these numbers and mark them.
If the number currently enumerated has been marked, there is no need to enumerate multiples (because the multiples of enumeration must also be marked).

Time complexity \ (\ mathcal{O}(n \log \log n) \).

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

const int SIZE = 1e7 + 500;

bool ori[SIZE + 10];
bool f[SIZE + 10];

int go[SIZE + 10]; 

void prework(int N) {
	for (int i = 1; i <= N; i ++)
		ori[i] = ori[i / 10] | (i % 10 == 7);

	for (int i = 1; i <= N; i ++) {
		if (!ori[i]) continue;
		if (f[i]) continue;
		for (int j = i; j <= N; j += i) f[j] = 1;
	}

	for (int i = N; i >= 1; i --)
		if (f[i])
			go[i] = go[i + 1];
		else
			go[i] = i;
}

void work() {
	int x = read();

	if (f[x])
		puts("-1");
	else
		printf("%d\n", go[x + 1]);
}

int main() {
	prework(SIZE);

	int T = read();

	while (T --)
		work();

	return 0;
}

// I hope changle_cyx can pray for me.

T2. series

Note that adding a number directly after the sequence will be difficult to maintain. You can consider adding numbers to the sequence from small to large.

Let \ (f(i, j, h, S) \) indicate that the number of \ (j \) has been selected, the value range of the selected number is \ ([0, i] \), there are \ (H \) \ (1 \) in the \ ([0, i] \) bit in the binary representation, and the binary representation in \ ([i + 1, *] \) is the number of schemes when \ (S \).

Consider enumerating how many \ (i \) are selected. If \ (x \) pieces of \ (i \) are selected, there will be transfer:

The final answer is: \ (\ sum \ limits {uh + \ text {count} (s) \ Leq k} f (m, N, h, s) \).

Where \ (\ text{count}(S) \) represents the number of \ (1 \) under \ (S \) binary.

Time complexity \ (\ mathcal{O}(n^4m) \).

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

int power(int a, int b, int p) {
	int ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = 1ll * ans * a % p;
		a = 1ll * a * a % p;
	}
	return ans;
}

const int N = 35, M = 110; 
const int mod = 998244353;

int n, m, k;
int val[M];

int fact[N], inv[N];
int C(int n, int m) {
	return 1ll * inv[n - m] * inv[m] % mod * fact[n] % mod;
}

int f[M][N][N][N];

void add(int &x, long long d) {
	x = (x + d) % mod;
}

int cnt[N];

int main() {
	n = read(), m = read(), k = read();

	for (int i = 0; i <= m; i ++)
		val[i] = read();

	fact[0] = 1;
	for (int i = 1; i <= n; i ++) fact[i] = 1ll * fact[i - 1] * i % mod;
	inv[n] = power(fact[n], mod - 2, mod);
	for (int i = n - 1; i >= 0; i --) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

	for (int x = 0, cur = 1; x <= n; x ++, cur = 1ll * cur * val[0] % mod)
		f[0][x][x % 2][x / 2] = cur;

	for (int i = 1; i <= m; i ++) {
		for (int x = 0, cur = 1; x <= n; x ++, cur = 1ll * cur * val[i] % mod) {
			for (int j = x; j <= n; j ++) {
				for (int h = 0; h <= n; h ++) {
					for (int S = 0; S <= n; S ++) {
						if (!f[i - 1][j - x][h][S]) continue;
						int d = 1ll * f[i - 1][j - x][h][S] * C(j, x) % mod * cur % mod;
						add(f[i][j][h + (S + x) % 2][(S + x) / 2], d);
					}
				}
			}
		}
	}

	for (int S = 1; S <= n; S ++)
		cnt[S] = cnt[S ^ (S & -S)] + 1;

	int ans = 0;
	for (int h = 0; h <= n; h ++)
		for (int S = 0; S <= n; S ++)
			if (h + cnt[S] <= k) add(ans, f[m][n][h][S]);

	printf("%d\n", ans);

	return 0;
}

T3. variance

Simple processing can multiply the \ (n^2 \) of variance to:

Then, you only need to know the sum of values and the sum of squares of values of a sequence to calculate the variance of the sequence.

Remember the difference fraction group \ (b_i = a_i - a_{i - 1} \), then one operation on \ (I \) is equivalent to exchanging \ (b_i, b_{i + 1} \).

Due to the adjacent item exchange, and any number of operations can be performed.
Then the new difference group \ (\ {b '\} \) after all operations can be any arrangement of the original difference group \ (\ {b \} \).

One conclusion: the difference fraction group of the optimal solution must decrease first and then increase (that is, single valley).

According to this property, we can sort all \ (n - 1 \) difference values from small to large, and then add the difference values from small to large. Since the variance relationship is the relative size between the data, we might as well set a benchmark with a value of \ (0 \).

Let \ (\ text{sum}_i \) indicate the sum of the small difference values before \ (I \).

Let \ (f(i, S) \) mean: considering the first \ (i \) difference values, when the current sum of values is \ (S \), what is the minimum sum of squares of values.

If you add a number to the left end of the current sequence, there is a transition:

If you add a number to the right end of the current sequence, there is a transition:

The final answer is \ (\ min\{n \cdot f(n - 1, S) - S^2 \} \).

Set the value field as \ (m \), and it is obviously \ (\ mathcal{O}(n^2m) \) to do it directly.

However, it is noted that there are only \ (\ min(n, m) \) different numbers in the whole sequence \ (\ {a \} \), that is, there are no more than \ (\ min(n, m) \) effective difference values that are not \ (0 \) in the difference group, so it can be optimized to \ (\ mathcal{O}(\min(n, m) \cdot nm) \).

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

const int N = 10010, SZ = 500100;
const int inf = 0x3f3f3f3f;

int n, m, L, res;
int a[N], b[N];

int sum[N];

int p, q;
int f[2][SZ];

int main() {
	n = read();

	for (int i = 1; i <= n; i ++)
		a[i] = read(), m = max(m, a[i]);

	L = n * m;

	for (int i = 1; i < n; i ++) {
		b[i] = a[i + 1] - a[i];
		if (!b[i]) res ++;
	}

	sort(b + 1, b + n);

	for (int i = 1; i < n; i ++)
		sum[i] = sum[i - 1] + b[i];

	p = 0, q = 1;

	f[p][0] = 0;
	for (int S = 1; S <= L; S ++) f[p][S] = inf;

	for (int i = res + 1; i < n; i ++) {
		p ^= 1, q ^= 1;

		for (int S = 0; S <= L; S ++) f[p][S] = inf;
		for (int S = 0; S <= L; S ++) {
			f[p][S + sum[i]] = min(f[p][S + sum[i]], f[q][S] + sum[i] * sum[i]);
			f[p][S + b[i] * i] = min(f[p][S + b[i] * i], f[q][S] + 2 * S * b[i] + i * b[i] * b[i]);
		}
	}

	long long ans = 1e18;
	for (int S = 0; S <= L; S ++)
		ans = min(ans, 1ll * n * f[p][S] - 1ll * S * S);

	printf("%lld\n", ans);

	return 0;
}

T4. Chess game

(to be filled in...)