Submission #69538802

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <atcoder/all>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;
using mint = modint998244353;

// PASS GRAPH WO FUKUMU KOTO
int n;
int a[300000];
mint dp[300001][2];

signed main() {
    int i, j;

    cin >> n;
    rep(i, n) { cin >> a[i]; a[i]--; }
    
    dp[0][0] = 1;
    rep(i, n - 1) {
        rep(j, 2) {
            if (a[i] != -2) {
                if (a[i] != i + 1) {
                    if (j == 0) {
                        dp[i + 1][1] += dp[i][j];
                    }
                }
                else { //a[i] == i + 1
                    if (j == 1 && a[i] != i - 1) continue;
                    dp[i + 1][j] += dp[i][j];
                }
            }
            else { // a[i] == -1
                if (j == 0) {
                    dp[i + 1][1] += dp[i][j] * (n - 1);
                    dp[i + 1][0] += dp[i][j];
                }
                else {
                    dp[i + 1][j] += dp[i][j];
                }
            }
        }
    }

    rep(i, n) {
        rep(j, 2) {
           // cout << dp[i][j].val() << " ";
        }
     //   cout << endl;
    }

    mint ans = dp[n - 1][0] * n + dp[n - 1][1];

    cout << ans.val() << endl;
    return 0;
}

Submission Info

Judge Result