提出 #60296093

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 998244353;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    ll ans = 0;
    for (int rev = 0; rev <= 1; rev++) {
        if (rev == 1) reverse(A.begin(), A.end());
        for (int g = 1; g < N; g++) {
            if (N % g != 0) continue;
            vector<ll> dp = {0}, c = {1};
            for (int k = 0; k < N; k++) {
                vector<ll> nxt_dp(k + 2), nxt_c(k + 2);
                for (int l = 0; l <= k; l++) {
                    // 1 → 0 の寄与
                    if (A[k] == 0 || A[k] == -1) {
                        nxt_dp[l + 1] += dp[l];
                        if (rev == 0) nxt_dp[l + 1] += (ll)((k - l - l % g + g - 1) / g) * k % MOD * c[l];
                        else nxt_dp[l + 1] += (ll)((k - l - l % g + g - 1) / g) * (N - 1 - k) % MOD * c[l];
                        nxt_dp[l + 1] %= MOD;
                        if (nxt_dp[l + 1] < 0) nxt_dp[l + 1] += MOD;
                        nxt_c[l + 1] += c[l];
                        nxt_c[l + 1] %= MOD;
                    }
                    // 0 → 1 の寄与
                    if (A[k] == 1 || A[k] == -1) {
                        nxt_dp[l] += dp[l];
                        if (rev == 0) nxt_dp[l] += (ll)((l - (k - l) % g + g - 1) / g) * k % MOD * c[l];
                        else nxt_dp[l] += (ll)((l - (k - l) % g + g - 1) / g) * (N - 1 - k) % MOD * c[l];
                        nxt_dp[l] %= MOD;
                        if (nxt_dp[l] < 0) nxt_dp[l] += MOD;
                        nxt_c[l] += c[l];
                        nxt_c[l] %= MOD;
                    }
                }
                swap(dp, nxt_dp);
                swap(c, nxt_c);
            }
            for (int alpha = 1; alpha <= N - 1; alpha++) {
                int beta = N - alpha;
                if (gcd(alpha, beta) == g) {
                    if (rev == 0) ans += dp[alpha];
                    else ans -= dp[alpha];
                    ans %= MOD;
                    if (ans < 0) ans += MOD;
                }
            }
        }
    }
    cout << ans << "\n";
}

提出情報

ジャッジ結果