提出 #41971551

---

ソースコード 拡げる

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int countShifts(int N, const string& S) {
    // Count the number of '#'s in the original shift table
    int count = 0;
    for (char c : S) {
        if (c == '#') {
            count++;
        }
    }

    int result = 0;

    // Iterate over all possible divisors of N
    for (int M = 1; M * M <= N; M++) {
        if (N % M == 0) {
            // Calculate the number of shifts possible for this divisor M

            // Check if M is a valid divisor
            bool valid = true;
            for (int i = 0; i < M; i++) {
                for (int j = i + M; j < N; j += M) {
                    if (S[j] != S[i]) {
                        valid = false;
                        break;
                    }
                }
                if (!valid) {
                    break;
                }
            }

            if (valid) {
                // Calculate the number of possible shifts for this divisor
                int shifts = 1;
                for (int i = 0; i < count; i++) {
                    shifts = (shifts * 2) % MOD;
                }

                result = (result + shifts) % MOD;

                // Check if M is a proper divisor (not equal to N/M)
                if (M != N / M) {
                    valid = true;
                    for (int i = 0; i < N / M; i++) {
                        for (int j = i + N / M; j < N; j += N / M) {
                            if (S[j] != S[i]) {
                                valid = false;
                                break;
                            }
                        }
                        if (!valid) {
                            break;
                        }
                    }

                    if (valid) {
                        shifts = 1;
                        for (int i = 0; i < count; i++) {
                            shifts = (shifts * 2) % MOD;
                        }

                        result = (result + shifts) % MOD;
                    }
                }
            }
        }
    }

    return result;
}

int main() {
    int N;
    string S;
    cin >> N >> S;

    int result = countShifts(N, S);
    cout << result << endl;

    return 0;
}

提出情報

ジャッジ結果