結果
| 問題 | No.2605 Pickup Parentheses |
| ユーザー |
 umimel
|
| 提出日時 | 2024-01-12 23:22:36 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 591 ms / 2,000 ms |
| コード長 | 8,232 bytes |
| コンパイル時間 | 3,828 ms |
| コンパイル使用メモリ | 248,972 KB |
| 実行使用メモリ | 27,756 KB |
| 最終ジャッジ日時 | 2024-09-30 06:31:10 |
| 合計ジャッジ時間 | 11,736 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 68 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
enum Mode {
FAST = 1,
NAIVE = -1,
};
template <class T, Mode mode = FAST>
struct FormalPowerSeries : std::vector<T> {
using std::vector<T>::vector;
using std::vector<T>::size;
using std::vector<T>::resize;
using F = FormalPowerSeries;
F &operator+=(const F &g) {
for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] += g[i];
return *this;
}
F &operator+=(const T &t) {
assert(int((*this).size()));
(*this)[0] += t;
return *this;
}
F &operator-=(const F &g) {
for(int i = 0; i < int(std::min((*this).size(), g.size())); i++) (*this)[i] -= g[i];
return *this;
}
F &operator-=(const T &t) {
assert(int((*this).size()));
(*this)[0] -= t;
return *this;
}
F &operator*=(const T &t) {
for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= t;
return *this;
}
F &operator/=(const T &t) {
T div = t.inv();
for(int i = 0; i < int((*this).size()); ++i) (*this)[i] *= div;
return *this;
}
F &operator>>=(const int sz) const {
assert(sz >= 0);
int n = (*this).size();
(*this).erase((*this).begin(), (*this).begin() + std::min(sz, n));
(*this).resize(n);
return *this;
}
F &operator<<=(const int sz) const {
assert(sz >= 0);
int n = (*this).size();
(*this).insert((*this).begin(), (*this).begin() + sz, 0);
(*this).resize(n);
return *this;
}
F &operator%=(const F &g) { return *this -= *this / g * g; }
F &operator=(const std::vector<T> &v) {
int n = (*this).size();
for(int i = 0; i < n; ++i) (*this)[i] = v[i];
return *this;
}
F operator-() const {
F ret = *this;
return ret * -1;
}
F &operator*=(const F &g) {
if(mode == FAST) {
int n = (*this).size();
auto tmp = atcoder::convolution(*this, g);
for(int i = 0; i < n; ++i) (*this)[i] = tmp[i];
return *this;
} else {
int n = (*this).size(), m = g.size();
for(int i = n - 1; i >= 0; --i) {
(*this)[i] *= g[0];
for(int j = 1; j < std::min(i + 1, m); j++)
(*this)[i] += (*this)[i - j] * g[j];
}
return *this;
}
}
F &operator/=(const F &g) {
if(mode == FAST) {
int n = (*this).size();
(*this) = atcoder::convolution(*this, g.inv());
return *this;
} else {
assert(g[0] != T(0));
T ig0 = g[0].inv();
int n = (*this).size(), m = g.size();
for(int i = 0; i < n; ++i) {
for(int j = 1; j < std::min(i + 1, m); ++j)
(*this)[i] -= (*this)[i - j] * g[j];
(*this)[i] *= ig0;
}
return *this;
}
}
F operator+(const F &g) const { return F(*this) += g; }
F operator+(const T &t) const { return F(*this) += t; }
F operator-(const F &g) const { return F(*this) -= g; }
F operator-(const T &t) const { return F(*this) -= t; }
F operator*(const F &g) const { return F(*this) *= g; }
F operator*(const T &t) const { return F(*this) *= t; }
F operator/(const F &g) const { return F(*this) /= g; }
F operator/(const T &t) const { return F(*this) /= t; }
F operator%(const F &g) const { return F(*this) %= g; }
T eval(const T &t) const {
int n = (*this).size();
T res = 0, tmp = 1;
for(int i = 0; i < n; ++i) res += (*this)[i] * tmp, tmp *= t;
return res;
}
F inv(int deg = -1) const {
int n = (*this).size();
assert(mode == FAST and n and (*this)[0] != 0);
if(deg == -1) deg = n;
assert(deg > 0);
F res{(*this)[0].inv()};
while(int(res.size()) < deg) {
int m = res.size();
F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);
f.resize(m * 2), atcoder::internal::butterfly(f);
r.resize(m * 2), atcoder::internal::butterfly(r);
for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
f.erase(f.begin(), f.begin() + m);
f.resize(m * 2), atcoder::internal::butterfly(f);
for(int i = 0; i < m * 2; ++i) f[i] *= r[i];
atcoder::internal::butterfly_inv(f);
T iz = T(m * 2).inv();
iz *= -iz;
for(int i = 0; i < m; ++i) f[i] *= iz;
res.insert(res.end(), f.begin(), f.begin() + m);
}
res.resize(deg);
return res;
}
F &diff_inplace() {
int n = (*this).size();
for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;
(*this)[n - 1] = 0;
return *this;
}
F diff() const { F(*this).diff_inplace(); }
F &integral_inplace() {
int n = (*this).size(), mod = T::mod();
std::vector<T> inv(n);
{
inv[1] = 1;
for(int i = 2; i < n; ++i)
inv[i] = T(mod) - inv[mod % i] * (mod / i);
}
for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];
(*this)[0] = 0;
return *this;
}
F integral() const { return F(*this).integral_inplace(); }
F &log_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 1);
F f_inv = (*this).inv();
(*this).diff_inplace();
(*this) *= f_inv;
(*this).integral_inplace();
return *this;
}
F log() const { return F(*this).log_inplace(); }
F &deriv_inplace() {
int n = (*this).size();
assert(n);
for(int i = 2; i < n; ++i) (*this)[i] *= i;
(*this).erase((*this).begin());
(*this).push_back(0);
return *this;
}
F deriv() const { return F(*this).deriv_inplace(); }
F &exp_inplace() {
int n = (*this).size();
assert(n and (*this)[0] == 0);
F g{1};
(*this)[0] = 1;
F h_drv((*this).deriv());
for(int m = 1; m < n; m *= 2) {
F f((*this).begin(), (*this).begin() + m);
f.resize(2 * m), atcoder::internal::butterfly(f);
auto mult_f = [&](F &p) {
p.resize(2 * m);
atcoder::internal::butterfly(p);
for(int i = 0; i < 2 * m; ++i) p[i] *= f[i];
atcoder::internal::butterfly_inv(p);
p /= 2 * m;
};
if(m > 1) {
F g_(g);
g_.resize(2 * m), atcoder::internal::butterfly(g_);
for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];
atcoder::internal::butterfly_inv(g_);
T iz = T(-2 * m).inv();
g_ *= iz;
g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);
}
F t((*this).begin(), (*this).begin() + m);
t.deriv_inplace();
{
F r{h_drv.begin(), h_drv.begin() + m - 1};
mult_f(r);
for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];
}
t.insert(t.begin(), t.back());
t.pop_back();
t *= g;
F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));
v.resize(m);
t.insert(t.begin(), m - 1, 0);
t.push_back(0);
t.integral_inplace();
for(int i = 0; i < m; ++i) v[i] -= t[m + i];
mult_f(v);
for(int i = 0; i < std::min(n - m, m); ++i)
(*this)[m + i] = v[i];
}
return *this;
}
F exp() const { return F(*this).exp_inplace(); }
F &pow_inplace(long long k) {
int n = (*this).size(), l = 0;
assert(k >= 0);
if(!k) {
for(int i = 0; i < n; ++i) (*this)[i] = !i;
return *this;
}
while(l < n and (*this)[l] == 0) ++l;
if(l > (n - 1) / k or l == n) return *this = F(n);
T c = (*this)[l];
(*this).erase((*this).begin(), (*this).begin() + l);
(*this) /= c;
(*this).log_inplace();
(*this).resize(n - l * k);
(*this) *= k;
(*this).exp_inplace();
(*this) *= c.pow(k);
(*this).insert((*this).begin(), l * k, 0);
return *this;
}
F pow(const long long k) const { return F(*this).pow_inplace(); }
};
using mint = modint998244353;
using fps = FormalPowerSeries<mint, FAST>;
fps product_of_polynomial_sequence(vector<fps> F){
queue<fps> Q;
Q.push({1});
for(auto f : F) Q.push(f);
int cnt = 0;
while((int)Q.size()>1){
fps f = Q.front();
Q.pop();
fps g = Q.front();
Q.pop();
for(int i=0; i<(int)g.size(); i++) f.push_back(0);
f *= g;
Q.push(f);
}
return Q.front();
};
int main(){
int n, m; cin >> n >> m;
vector<mint> fac(2*n+1, 1);
for(int i=2; i<=2*n; i++) fac[i] = fac[i-1]*mint(i);
vector<mint> C(n+1, 1);
for(int i=1; i<=n; i++) C[i] = fac[2*i]/(fac[i+1]*fac[i]);
vector<fps> F;
int D = 0;
for(int i=0; i<m; i++){
int L, R; cin >> L >> R;
if((R-L+1)%2==1) continue;
D += R-L+1;
fps f(R-L+2, 0);
f[0] = 1;
f[R-L+1] = -C[(R-L+1)/2];
F.push_back(f);
}
if(n%2==1){
cout << 0 << '\n';
return 0;
}
fps v = product_of_polynomial_sequence(F);
mint ans = 0;
for(int i=0; i<=D; i++){
if(i%2==1) continue;
ans += v[i] * C[(n-i)/2];
}
cout << ans.val() << '\n';
}