#1157038 (C++23) No.1204 お菓子配り-FINAL

• 問題: No.1204 お菓子配り-FINAL
• ユーザー: tanjiaqi2027-code
• 提出日時: 2026-04-11 09:18:23
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,343 ms / 8,000 ms
• コード長: 3,652 bytes
• コンパイル時間: 1,383 ms
• コンパイル使用メモリ: 174,928 KB
• 実行使用メモリ: 7,972 KB
• 最終ジャッジ日時: 2026-04-11 09:18:46
• 合計ジャッジ時間: 21,982 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
other	AC * 130

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

long long MOD = 1000000007;

// 快速幂
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

long long fac[200010], invFac[200010];

void prepare() {
    fac[0] = 1;
    for (int i = 1; i < 200010; i++) fac[i] = (fac[i - 1] * i) % MOD;
    invFac[200009] = modInverse(fac[200009]);
    for (int i = 200008; i >= 0; i--) invFac[i] = (invFac[i + 1] * (i + 1)) % MOD;
}

// 核心计数公式：(n - k + 1) * (n + 1)^(k - 1)
// 基于镜像法/圆周法推导的停车场函数计数
long long calc(int n, int k) {
    if (k == 0) return 1;
    long long res = (n - k + 1 + MOD) % MOD;
    res = (res * power(n + 1, k - 1)) % MOD;
    return res;
}

struct Query {
    string s;
    int sig;
};

vector<Query> qss[105];

// 容斥处理：处理照片两端的 '-'
void pie(string s, int sig) {
    if (!s.empty() && s.front() == '-') {
        pie(s.substr(1), sig);
        string next_s = s;
        next_s[0] = 'o';
        pie(next_s, -sig);
    } else if (!s.empty() && s.back() == '-') {
        pie(s.substr(0, s.size() - 1), sig);
        string next_s = s;
        next_s.back() = 'o';
        pie(next_s, -sig);
    } else {
        qss[s.size()].push_back({s, sig});
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    prepare();

    int N, M;
    while (cin >> N >> M) {
        string S;
        cin >> S;

        for (int i = 0; i <= M; i++) qss[i].clear();
        pie(S, 1);

        long long ans = 0;

        // 处理长度减少到 0 的特殊情况
        int sigSum = 0;
        for (auto &q : qss[0]) sigSum = (sigSum + q.sig + MOD) % MOD;
        if (sigSum != 0) {
            long long term = (power(N, N) * (N + 1)) % MOD;
            ans = (ans + sigSum * term) % MOD;
        }

        // 处理剩下的容斥块
        for (int m = 1; m <= M; m++) {
            if (qss[m].empty()) continue;

            vector<long long> nums(m + 1, 0);
            for (auto &q : qss[m]) {
                int insideSum = 0;
                long long insideNum = 1;
                for (int i = 0; i < m; ) {
                    int j = i;
                    while (j < m && q.s[i] == q.s[j]) j++;
                    if (q.s[i] == '-') {
                        int len = j - i;
                        insideSum += len;
                        long long c = (calc(len, len) * invFac[len]) % MOD;
                        insideNum = (insideNum * c) % MOD;
                    }
                    i = j;
                }
                nums[insideSum] = (nums[insideSum] + q.sig * insideNum + MOD) % MOD;
            }

            for (int l = 0; l <= m; l++) {
                if (nums[l] == 0) continue;
                long long sum_k = 0;
                for (int k = 0; k <= N - m; k++) {
                    long long term = calc(N - m, k);
                    term = (term * invFac[k]) % MOD;
                    term = (term * fac[k + l]) % MOD;
                    term = (term * power(N, N - (k + l))) % MOD;
                    sum_k = (sum_k + term) % MOD;
                }
                ans = (ans + nums[l] * sum_k) % MOD;
            }
        }

        // 最后乘以照片可能出现的所有位置 (N - M + 1)
        ans = (ans * (N - M + 1)) % MOD;
        cout << ans << endl;
    }

    return 0;
}