20260918 每日 1.0 3.0 4.0

No.3279 Dhole vs Monster

https://yukicoder.me/problems/no/3279

namespace XK {
  void solve() {
  	int f[] = {0, 390,429,468,507,546};
  	int x; string t; cin >> x >> t;
  	if(t == "Beat") cout << f[x + 1];
  	else cout << f[x];
  }
};

No.2899 Taffy Permutation

https://yukicoder.me/problems/no/2899

这是3.0？

首先我们会发现，0 与 0 之间，1 与 1 之间没有约束，于是我们会想到定义：

$f_{i,k} :=$ 考虑到第 $i$ 位的时候，当前 $max(P_{S_i=0}) = k$ 的数量

我们会发现无法约束 1 的选法，也不能统计还需要多少，而再加一维度则不能通过，考虑转化。

我们会想到，$k$ 的大小并不影响选法，影响选法的是，$\lt k$ 的部分剩下的可选点，于是定义：

$f_{i,j} :=$ 考虑到第 $i$ 位的时候，当前比 $max(P_{S_i=0})$ 小的还没有用的数字数量刚好是 $j$ 的方案数

下面考虑状态转移：

• 当 $S_i = 1$ 的时候，那么你只能选比 $max(P_{S_i=0})$ 大的数，此时如果只考虑选过的数，那么可选点是 $N - i$ 个，然后减去还没用的数字数量，也就是 $N - i - j$ 个可选点，转移就是。这里，添加 1 不会影响 $j$ 的数量。
  • $f_{i,j} := f_{i - 1,j} \times (N - i - j)$
• 当 $S_i = 0$ 的时候，有两种情况，一是更新 $max(P_{S_i=0})$，二是不更新。
  • 更新的时候，不会影响 $j$ 的数量，因为你的选点依旧在 $max$ 以外，而更新的来源可以从比 $j$ 小的任意一个位置来，于是有转移
    • $f_{i,j} := \sum_{k=0}^j f_{i-1,k}$
  • 不更新的时候，$j$ 的数量会 $-1$，这里考虑选点即可，选点刚好是 $j$ 个，于是有转移
    • $f_{i,j-1} := f_{i-1,j} \times j$

接下来考虑初始值：

• 当 $S_0=0$ 的时候，对于每一个 $j$ 都存在约束，于是有
  • $f_{0,i} = 1, i\in [0,N]$
• 当 $S_0 = 1$ 的时候，不存在 $j$，但第一个选点可以是任意的，于是
  • $f_{0,0} = N$

答案就是 $f_{N-1,0}$，这是显然的，因为你要全部填完。

复杂度是 $O(N^2)$ 的，空间复杂度可以通过滚动数组优化到 $O(N)$，但本题目不要求优化。

namespace XK {
const ll mod = 998244353;
struct mm {
};
  void solve() {
  	int N; cin >> N; string S; cin >> S;
  	V<V<mm>> f(N, V<mm>(N + 1, 0));
  	if(S[0] == '1') f[0][0] = N;
  	else rep(i, N + 1) f[0][i] = 1;
  	Rep(i, 1, N) {
  		if(S[i] == '1') {
  			rep(j, N + 1) if(i + j < N) f[i][j] += f[i - 1][j] * (N - i - j);
  		} else {
  			auto nf = f[i - 1];
  			Rep(j, 1, N + 1) nf[j] += nf[j - 1];
  			rep(j, N + 1) f[i][j] += nf[j];
  			Rep(j, 1, N + 1) f[i][j - 1] += f[i - 1][j] * j;
  		}
  	}
  	cout << f[N - 1][0].x;
  }
};

今天的4.0是早期4.0，打暴力就能通过，不在这里放了