目录

H. Genshin Impact Startup Forbidden III

 K. Points on the Number Axis B

---

估计还会补D，I

H. Genshin Impact Startup Forbidden III

对于一个有鱼的池塘，有周围与自己本身五个关键位置可以捕获当前位位置的鱼。把这些位置存储到 map中。用四进制数 S 表示每块池塘中剩余的鱼的数目，dp[S] 表示达成该状态最少的炸弹数。枚举所有的关键位置，计算状态的转移。

#define PII pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 1e9 + 7;
map < PII, vector<int>>mp;
PII pos[5] = { {0,0},{0,1},{1,0},{-1,0},{0,-1} };
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	vector<int>pow(15);
	pow[0] = 1;
	for (int i = 1; i < 11; i++) {
		pow[i] = pow[i - 1] * 4;
	}
	int n, m, k;
	cin >> n >> m >> k;
	vector<int>val;
	int res = 0;
	for (int I = 0; I < k; I++)
	{
		int x, y, a;
		cin >> x >> y >> a;
		val.push_back(a);
		res += int(a*pow[I]);
		for (int i = 0; i < 5; i++)
		{
			int xx = x + pos[i].first, yy = y + pos[i].second;
			if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue;
			mp[{xx, yy}].push_back(I);
		}
	}
	auto check = [&](int x)
	{
		for (int i = 0; i < k; i++) {
			if (x % 4 > val[i]) return true;
			x /= 4;
		}
		return false;
	};
	auto check2 = [&](int x, int y)
	{
		for (int i = 0; i < y; i++) {
			x /= 4;
		}
		if (x % 4 == val[y]) return true;
		return false;
	};
	vector<int>dp(int(pow[ k]),inf);
	dp[0] = 0;
	for (int i = 0; i<int(pow[k]); i++) {
		if (check(i)) continue;
		for (auto w : mp) {
			vector<int>& tmp = w.second;
			int t = i;
			for (auto ww : tmp) {
				if (check2(t,ww)) continue;
				t += int(pow[ww]);
			}
			dp[t] = min(dp[t], dp[i] + 1);
		}
	}
	cout << dp[res];
}
 

 K. Points on the Number Axis B

#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e6 + 5, mod = 998244353;
void add(int& x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}
int binpow(int a, int b) {
	if (!b) return 1;
	if (b & 1) return 1ll * a * binpow(a, b - 1) % mod;
	return binpow(1ll * a * a % mod, b >> 1);
}
int n, a[N], dp[N];
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		dp[i] = 1ll * dp[i - 1] * (i + i - 1) % mod;
		dp[i] = 1ll * dp[i] * binpow(i + i, mod - 2) % mod;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) add(ans, 1ll * a[i] * dp[i] % mod * dp[n - i - 1] % mod);
	cout << ans;
}