日记详情

怎么看了题解之后认为我是智障啊。

---

• 若 \(s_i=0\) 则随便选，扔到未知的垃圾桶里。

• 若 \(s_i=1\) 则有两种情况，设当前有 \(x\) 个人被扔到垃圾桶里了。

  • 若 \(c_i>x\) 则是成功的
  • 若 \(c_i\le x\) 则扔到垃圾桶里

然后这俩东西可以转化成一个就是把 \(c_i>x\) 看成 \(c_i\le x\) 那么方案数就是要减去的。

有 \(f_{i,j,k}\) 表示对于前 \(i\) 个数，有 \(j\) 个人在垃圾桶，有 \(k\) 个人确定位置。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
// char buf[1 << 21], *p1 = buf, *p2 = buf;
#define scin static inline
#define per(i, a, b) for (int i = a, END##i = b; i >= END##i; i--)
#define rep(i, a, b) for (int i = a, END##i = b; i <= END##i; i++)
typedef vector<int> vi;
typedef unsigned long long ull;
typedef pair<int ,int> pii;
typedef pair<ll, ll> pll;
// #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// #define getchar() gc()
template <typename T> scin void rd(T& s) {s = 0; char ch = getchar(); bool fu = 0;while (ch < '0' || ch > '9') ch == '-' ? fu = 1 : 0, ch = getchar();while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();s = fu ? -s : s;
}template <typename T, typename...Args> scin void rd(T& s, Args& ...args) {rd(s), rd(args...);}
template <typename T> scin bool updmin(T& a,T& b) {return a > b ? a = b, true : false;}
template <typename T> scin bool updmax(T& a,T& b) {return a < b ? a = b, true : false;}
template <typename T> scin void updmod(T& a) {a >= mod ? a -= mod : 0;}
template <typename T> scin T updmod(T a,T b) {return a + b >= mod ? a + b - mod : a + b;}const int N = 510;
int f[N][N][N], n, m, c, rk[N], fac[N];
char s[N];
// 对于前 i 个数，已经有 j 个在垃圾桶，k 个确定位置
void Solve() {fac[0] = 1;for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;rd(n, m);cin >> s + 1;for (int i = 1, c; i <= n; ++i) rd(c), ++rk[c];for (int i = 1; i <= n; ++i) rk[i] += rk[i - 1];f[0][0][0] = 1;for (int i = 0; i < n; ++i) {if (s[i + 1] == '0') {for (int j = 0; j <= i; ++j)for (int k = 0; k <= i; ++k)(f[i + 1][j + 1][k] += f[i][j][k]) %= mod;} else {for (int j = 0; j <= i; ++j)for (int k = 0; k <= i; ++k) {(f[i + 1][j][k] += f[i][j][k]) %= mod;int x = rk[j] - k;(f[i + 1][j][k + 1] -= 1ll * x * f[i][j][k] % mod) %= mod;(f[i + 1][j + 1][k + 1] += 1ll * x * f[i][j][k] % mod) %= mod;}}}int ans = 0;for (int j = 0; j <= n - m; ++j)for (int k = 0; k <= n; ++k)(ans += 1ll * f[n][j][k] * fac[n - k] % mod) %= mod;cout << (ans + mod) % mod << "\n";
}signed main() {// freopen("input.in", "r", stdin);// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T = 1;// rd(T);while (T--) Solve();return 0;
}