結果

問題 No.1204 お菓子配り-FINAL
コンテスト
ユーザー vjudge1
提出日時 2026-04-11 10:19:56
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 960 ms / 8,000 ms
コード長 2,753 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,737 ms
コンパイル使用メモリ 340,492 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-04-11 10:20:17
合計ジャッジ時間 19,001 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 130
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int Md = 1e9 + 7;
const int N = 1e5 + 5;
ll qpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % Md;
        a = a * a % Md;
        b >>= 1;
    }
    return ret;
}
ll fac[N], rev[N];
void init(void) {
    fac[0] = rev[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = (fac[i - 1] * i) % Md;
        rev[i] = (rev[i - 1] * qpow(i, Md - 2)) % Md;
    }
}
ll calc(int n, int k) {
    if (k == 0) return 1;
    ll res = ((n - k + 1) % Md + Md) % Md;
    return (res * qpow(n + 1, k - 1)) % Md;
}
vector<pair<string, int>> blocks[N];
void solve(string s, int invert) {
    if (!s.empty() && s.front() == '-') {
        solve(s.substr(1), invert);
        string nxt_s = s;
        nxt_s[0] = 'o';
        solve(nxt_s, -invert);
    }
    else if (!s.empty() && s.back() == '-') {
        solve(s.substr(0, s.size() - 1), invert);
        string nxt_s = s;
        nxt_s.back() = 'o';
        solve(nxt_s, -invert);
    }
    else
        blocks[s.size()].emplace_back(s, invert);
}
int n, m;
string s;
int main() {
    FASTIO;
    init();
    cin >> n >> m >> s;
    solve(s, 1);
    ll ans = 0, sum = 0;
    for (auto q : blocks[0])
        sum = (sum + q.second + Md) % Md;
    if (sum != 0)
        ans = (ans + sum * qpow(n, n) % Md * (n + 1) % Md) % Md;
    for (int sss = 1; sss <= m; ++sss) {
        if (blocks[sss].empty())
            continue;
        vector<long long> nums(sss + 1, 0);
        for (auto& q : blocks[sss]) {
            int cnt = 0;
            long long cnt1 = 1;
            for (int i = 0; i < sss; ) {
                int j = i;
                while (j < sss && q.first[i] == q.first[j]) j++;
                if (q.first[i] == '-') {
                    int len = j - i;
                    cnt += len;
                    long long c = (calc(len, len) * rev[len]) % Md;
                    cnt1 = (cnt1 * c) % Md;
                }
                i = j;
            }
            nums[cnt] = (nums[cnt] + q.second * cnt1 + Md) % Md;
        }
        for (int l = 0; l <= sss; l++) {
            if (nums[l] == 0) continue;
            long long sum_k = 0;
            for (int k = 0; k <= n - sss; k++) {
                long long term = calc(n - sss, k);
                term = (term * rev[k]) % Md;
                term = (term * fac[k + l]) % Md;
                term = (term * qpow(n, n - (k + l))) % Md;
                sum_k = (sum_k + term) % Md;
            }
            ans = (ans + nums[l] * sum_k) % Md;
        }
    }
    ans = (ans * (n - m + 1)) % Md;
    cout << ans << endl;
    return 0;
}
0