Submission #60593797

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 2e5 + 7;
int n, a[N], s[N], f[N], fac[N], invfac[N];
int qpow(int a, int b) {
    int ret = 1;
    while(b) {
        if(b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ret;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    bool flag = true;
    for(int i = 1; i < n; i++) if((a[i] != i % 2) && (a[i + 1] != (i + 1) % 2)) flag = false;
    fac[0] = fac[1] = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 2e5 + 7;
int n, a[N], s[N], f[N], fac[N], invfac[N];
int qpow(int a, int b) {
    int ret = 1;
    while(b) {
        if(b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ret;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    bool flag = true;
    for(int i = 1; i < n; i++) if((a[i] != i % 2) && (a[i + 1] != (i + 1) % 2)) flag = false;
    fac[0] = fac[1] = 1;
    for(int i = 2; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    for(int i = 1; i <= n; i++) invfac[i] = qpow(fac[i], mod - 2);
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= i; j++) {
            f[i] = (f[i] + 1ll * f[i - j] * invfac[j] % mod) % mod;
        }
    }
    if(!flag || (a[1] != 1) || (a[n] != n % 2)) {
        puts("0");
        return;
    }
    int ans = 1, all = 0;
    // cout << 1ll * fac[5] * f[5] % mod << endl;
    for(int i = 1, j; i <= n; i = j) {
        j = i;
        if(a[j] % 2 == (j % 2)) {j ++ ; continue;}
        int cnt = 1;
        while(j + 2 <= n && a[j + 2] != (j + 2) % 2) j += 2, cnt ++ ;
        // cout << i << " " << "cnt = " << cnt << endl;
        ans = 1ll * ans * f[cnt] % mod;
        all += cnt;
        j ++ ;
    }
    ans = 1ll * ans * fac[all] % mod;
    cout << ans << endl;
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; T = 1;
    for(int _ = 1; _ <= T; _ ++) solve();
    return 0;
}

Submission Info

Judge Result