ARC124A LR Constraint

tony102

2021 年 11 月 12 日

1343 次浏览

暂无评论

378字数

题解

[Link](https://atcoder.jp/contests/arc124/tasks/arc124_a)

## Sol

怎么 A 题就开始计数啊？？？不对劲（思想还在三年前）

手模了一下第二个样例，发现 `L` ，`R` 相当于限制了以它为尾的前后缀。以 `L` 为例，假如它填的是 $x$ ，若它的位置 $p_i <x $  相当于没限制。`R` 同理。所以只需要统计一下每个位置有效限制了多少个数然后乘起来就可以了。

## Idea

1. 最近出了不少这种计数，就是符合计数条件的东西其实很浅显（不需要 dp 或者组合容斥之类的）。需要分析限制的性质，然后直接计数。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 1e3 + 5;
const int mod = 998244353;

int n, k;
int s[SIZE]; bool vis[SIZE];

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

signed main() {
    cin >> n >> k;
    for (int i = 1; i <= k; ++ i) {
        char ch; int x; cin >> ch >> x;
        vis[x] = 1;
        for (int j = 1; j <= n; ++ j) {
            if (ch == 'L' && x <= j) ++ s[j];
            if (ch == 'R' && j <= x) ++ s[j];
        }
    }
    int ans = 1ll;
    for (int i = 1; i <= n; ++ i) {
        if (!vis[i]) ans = ans * s[i] % mod;
    }
    printf("%lld\n", ans);
    return 0;
}
```

最后修改：2021 年 11 月 12 日