1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| #include <iostream> #include <numeric> #include <algorithm> #include <vector> #include <queue> #define ll long long #define maxn 210 #define INF 1000000000 using namespace std;
const int p = 998244353; inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } inline int mul(int x, int y) { return 1ll * x * y % p; } inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; } int pow_mod(int x, int n) { int s = 1; for (; n; n >>= 1, x = mul(x, x)) if (n & 1) s = mul(s, x); return s; }
int n, m, st, a[maxn], b[maxn], s[maxn];
int C[maxn][maxn]; void init_C(int n) { for (int i = 0; i <= n; ++i) C[i][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); }
int g[maxn][maxn], f[maxn][maxn]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> m >> n >> st; init_C(n); const int inv = pow_mod(m, p - 2); int k = 0; for (int i = 1; i <= n; ++i) { cin >> b[i]; if (b[i] == st) k = i; } if (n == 1) return cout << 1 << "\n", 0; for (int i = 2; i <= n; ++i) a[i] = b[i] - b[i - 1]; a[1] = m - b[n] + b[1]; for (int i = 1; i <= n; ++i) b[i] = a[i]; for (int i = 1; i <= n - k; ++i) a[i] = b[i + k]; for (int i = n - k + 1; i <= n; ++i) a[i] = b[i - (n - k)]; for (int i = 1; i <= n; ++i) s[i] = add(s[i - 1], a[i]); for (int i = 1; i <= n; ++i) g[i][i] = 1; for (int l = 2; l <= n; ++l) for (int i = 1, j = l; j <= n; ++i, ++j) for (int k = i; k < j; ++k) g[i][j] = add(g[i][j], mul({ C[j - i - 1][k - i], add(s[k], p - s[i - 1]), inv, g[i][k], g[k + 1][j] })); f[0][0] = 1; int ans = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) for (int k = 0; k < i; ++k) { if (k < (j - 1)) continue; int t = mul({ f[k][j - 1], C[i - j][k - (j - 1)], g[k + 1][i] }); f[i][j] = add(f[i][j], mul({ f[k][j - 1], C[i - j][k - (j - 1)], g[k + 1][i] })); if (i == n) ans = add(ans, mul({ t, add(s[i], p - s[k]), inv })); } for (int i = 1; i <= n; ++i) ans = add(ans, f[n][i]); cout << add(ans, p - 1) << "\n"; return 0; }
|