結果
| 問題 | No.1204 お菓子配り-FINAL |
| コンテスト | |
| ユーザー |
 vjudge1
|
| 提出日時 | 2026-04-11 10:14:13 |
| 言語 | C++14 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,242 bytes |
| 記録 | |
| コンパイル時間 | 1,323 ms |
| コンパイル使用メモリ | 98,660 KB |
| 実行使用メモリ | 6,912 KB |
| 最終ジャッジ日時 | 2026-04-11 10:14:34 |
| 合計ジャッジ時間 | 14,666 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 118 WA * 12 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int G = 3; // MOD 1000000007 ???
// ---------------- ????????? ----------------
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
if (base < 0) 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);
}
const int MAX = 200005;
long long fact[MAX], invFact[MAX];
void precompute() {
fact[0] = 1; invFact[0] = 1;
for (int i = 1; i < MAX; i++) fact[i] = (fact[i - 1] * i) % MOD;
invFact[MAX - 1] = modInverse(fact[MAX - 1]);
for (int i = MAX - 2; i >= 1; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
// ???????????: f(l) = (l+1)^(l-1) / l!
long long f(long long l) {
if (l == 0) return 1;
return power(l + 1, l - 1) * invFact[l] % MOD;
}
// ?????? O(1) ????: [w^n] F(w)^m
long long get_c(long long m, long long n) {
if (m == 0) return (n == 0) ? 1 : 0;
if (n == 0) return 1;
long long base = (n + m) % MOD;
long long p = power(base, n - 1);
long long ans = m % MOD * p % MOD;
return ans * invFact[n] % MOD;
}
// ---------------- NTT ??????? ----------------
void ntt(vector<long long>& a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
long long wlen = power(G, (MOD - 1) / len);
if (invert) wlen = modInverse(wlen);
for (int i = 0; i < n; i += len) {
long long w = 1;
for (int j = 0; j < len / 2; j++) {
long long u = a[i + j], v = a[i + j + len / 2] * w % MOD;
a[i + j] = (u + v < MOD ? u + v : u + v - MOD);
a[i + j + len / 2] = (u - v >= 0 ? u - v : u - v + MOD);
w = w * wlen % MOD;
}
}
}
if (invert) {
long long n_inv = modInverse(n);
for (long long& x : a) x = x * n_inv % MOD;
}
}
// ????? O(N log N)
vector<long long> multiply_NTT(vector<long long> const& a, vector<long long> const& b) {
if (a.empty() || b.empty()) return {};
vector<long long> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size()) n <<= 1;
fa.resize(n); fb.resize(n);
ntt(fa, false); ntt(fb, false);
for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
ntt(fa, true);
vector<long long> res(a.size() + b.size() - 1);
for (int i = 0; i < res.size(); i++) res[i] = fa[i];
return res;
}
// ---------------------------------------------------
int main() {
// ?? IO ??
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute();
long long N, M;
if (!(cin >> N >> M)) return 0;
string S;
cin >> S;
int c = 0;
bool has_o = false;
for (char ch : S) {
if (ch == '-') c++;
if (ch == 'o') has_o = true;
}
int V = N - M;
long long ans = 0;
if (has_o) {
// ==========================================
// ?? 1: ?? S ????? 'o'?????
// ==========================================
int first_o = -1, last_o = -1;
for (int i = 0; i < M; ++i) {
if (S[i] == 'o') {
if (first_o == -1) first_o = i;
last_o = i;
}
}
int a = first_o;
int b = M - 1 - last_o;
// ?????????????????? W_{in}
long long Win = 1;
int current_dash = 0;
for (int i = first_o + 1; i <= last_o; ++i) {
if (S[i] == '-') {
current_dash++;
} else {
Win = Win * f(current_dash) % MOD;
current_dash = 0;
}
}
// ???????? P_a(x) ? P_b(x)
vector<long long> Pa(a, 0), Pb(b, 0);
for (int i = 0; i < a; ++i) Pa[i] = f(i);
for (int i = 0; i < b; ++i) Pb[i] = f(i);
// O(M log M) ?? NTT ??????? P_a * P_b
vector<long long> Q;
int degQ = -1;
if (a > 0 && b > 0) {
Q = multiply_NTT(Pa, Pb);
degQ = Q.size() - 1;
}
// ????????? R(x)
int degR = max(a, b) - 1;
vector<long long> R;
if (degR >= 0) {
R.assign(degR + 1, 0);
for (int i = 0; i < a; ++i) R[i] = (R[i] + Pa[i]) % MOD;
for (int i = 0; i < b; ++i) R[i] = (R[i] + Pb[i]) % MOD;
}
// ?????????? k
for (int k = 0; k <= V; ++k) {
long long Wk = 0;
if (k == V) {
// ????????????????
Wk = f(a + V + b) * Win % MOD;
} else {
long long T1 = get_c(V - k + 1, k + a + b);
long long T2 = 0;
if (degR >= 0) {
for (int i = 0; i <= degR; ++i) {
if (R[i]) T2 = (T2 + R[i] * get_c(V - k, k + a + b - i)) % MOD;
}
}
long long T3 = 0;
if (degQ >= 0) {
for (int j = 0; j <= degQ; ++j) {
if (Q[j]) T3 = (T3 + Q[j] * get_c(V - k - 1, k + a + b - j)) % MOD;
}
}
Wk = (T1 - T2 + T3) % MOD;
if (Wk < 0) Wk += MOD;
Wk = Wk * Win % MOD;
}
long long K = c + k;
long long term = Wk * fact[K] % MOD * power(N, N - K) % MOD;
ans = (ans + term) % MOD;
}
} else {
// ==========================================
// ?? 2: ?? S ???? '-'?????????
// ==========================================
for (int k = 0; k <= V; ++k) {
if (k == V) {
// ????????K = N ????????????? N^N ?????
ans = (ans + power(N, N)) % MOD;
} else {
long long K = M + k; // ???????
long long m = V - k - 1; // ????????????
// ????????????????
long long TermAB_coef = (K - (M - 1) * (m + 1) % MOD + MOD) % MOD;
long long TermAB = 0;
if (K > 0) {
TermAB = TermAB_coef * power(K + m + 1, K - 1) % MOD * invFact[K] % MOD;
}
long long TermC = 0;
for (int n = 0; n < M; ++n) {
long long coef = (M - 1 - n + MOD) % MOD;
long long val = coef * f(n) % MOD * get_c(m, K - n) % MOD;
TermC = (TermC + val) % MOD;
}
long long Wk = (TermAB + TermC) % MOD;
long long ways = Wk * fact[K] % MOD * power(N, N - K) % MOD;
ans = (ans + ways) % MOD;
}
}
}
// ??????????????? (N - M + 1) ?????????
ans = ans * (N - M + 1) % MOD;
cout << ans << "\n";
return 0;
}