알파카컵 1회: F - 알파카의 끝없는 울음소리
플래티넘 II의견: 0
알파카 왕국에는 길이 \(N\)의 울음소리 문자열을 만드는 의식이 있다.
울음소리는 알파벳 소문자 중 처음 \(C\)개의 문자만 사용해서 만든다. 즉 사용할 수 있는 문자는 \('a', 'b', \dots , char('a' + C - 1)\)이다.
알파카 사제들은 특정 문자열 \(P\)를 신성한 패턴이라고 부른다. 길이 \(N\)의 문자열 \(S\)에 대해, \(P\)가 \(S\) 안에 부분 문자열로 등장하는 횟수를 센다. 등장은 서로 겹칠 수 있다.
예를 들어 \(P = \texttt{aa}\), \(S = \texttt{aaa}\)라면 \(P\)는 2번 등장한다.
aa-
-aa
알파카 왕은 길이 \(N\)의 가능한 모든 울음소리 중에서, 신성한 패턴 \(P\)가 정확히 \(K\)번 등장하는 문자열의 개수를 알고 싶어 한다.
정답을 \(1,000,000,007\)로 나눈 나머지를 출력하시오.
- \(1 \le N \le 10^{18}\)
- \(1 \le C \le 26\)
- \(0 \le K \le 5\)
- \(1 \le |P| \le 60\)
- \(P\)는 알파벳 소문자로만 이루어져 있으며, \(P\)의 모든 문자는 사용 가능한 \(C\)개의 문자 중 하나이다.
첫째 줄에 세 정수 \(N\), \(C\), \(K\)가 주어진다.
둘째 줄에 문자열 \(P\)가 주어진다.
조건을 만족하는 길이 \(N\)의 문자열 개수를 \(1,000,000,007\)로 나눈 나머지를 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
서브태스크 1 | 10점 | \(N \le 10\), \(|P| \le 5\), \(C \le 3\), \(K \le 5\) |
서브태스크 2 | 20점 | \(N \le 2000\), \(|P| \le 60\), \(K \le 5\) |
서브태스크 3 | 30점 | \(N \le 10^9\), \(|P| \le 30\), \(K \le 3\) |
서브태스크 4 | 40점 | 전체 제한 (\(N \le 10^{18}\), \(|P| \le 60\), \(K \le 5\)) |
3 1 2
aa1사용 가능한 문자는 'a' 하나뿐이다. 길이 3의 문자열은 "aaa" 하나뿐이고, "aa"는 2번 등장한다.
3 2 1
ab4사용 가능한 문자는 'a', 'b'이다. 길이 3의 문자열 중 "ab"가 정확히 한 번 등장하는 문자열은 "aab", "aba", "abb", "bab"의 4개이다. (각각 "ab"가 한 번씩 들어 있다.)
4 2 0
aa8길이 4의 이진 문자열 중 "aa"가 한 번도 등장하지 않는 문자열은 8개이다.
해설
알파카컵 1회: F - 알파카의 끝없는 울음소리
알파카컵 1회: F - 알파카의 끝없는 울음소리
1. 문제 요약
알파벳 소문자 중 처음 \(C\)개의 문자만 사용하여 만든 길이 \(N\)의 문자열 \(S\) 중에서, 신성한 패턴 \(P\)가 (서로 겹치는 것을 허용하여) 부분 문자열로 정확히 \(K\)번 등장하는 것의 개수를 구해야 합니다. \(N\)이 최대 \(10^{18}\)으로 매우 크고, 정답은 \(1{,}000{,}000{,}007\)로 나눈 나머지를 출력합니다.
이 문제의 핵심은 두 가지입니다.
- 문자열을 한 글자씩 이어 붙일 때, 현재까지 만든 접미사가 패턴 \(P\)와 얼마나 일치하는지(KMP 오토마톤의 상태)를 추적하는 것
- 지금까지 패턴이 몇 번 등장했는지(\(0\)번부터 \(K\)번까지)를 함께 추적하는 것
이 두 정보를 하나의 상태로 묶어 동적 계획법(DP)을 설계하고, \(N\)의 크기에 따라 점화식을 직접 반복하거나 행렬 거듭제곱으로 가속하는 것이 풀이의 골격입니다.
2. [서브태스크 1]: \(N \le 10\), \(|P| \le 5\), \(C \le 3\), \(K \le 5\)
\(N\)이 최대 \(10\)이고 사용 가능한 문자가 최대 \(3\)개뿐이므로, 가능한 모든 문자열의 개수는 \(C^N \le 3^{10} = 59049\)로 매우 작습니다. 따라서 모든 문자열을 직접 만들어 보고 조건을 확인하는 완전 탐색으로 충분히 통과할 수 있습니다.
-
풀이: \(0\)부터 \(C^N - 1\)까지의 정수를 \(C\)진법으로 해석하여 길이 \(N\)의 모든 문자열을 하나씩 생성합니다. 각 문자열에 대해 패턴 \(P\)가 등장하는 횟수를 단순 비교로 직접 세고, 그 값이 정확히 \(K\)와 같은 문자열의 개수를 누적합니다. 등장은 겹쳐도 되므로 시작 위치를 한 칸씩 옮겨 가며 모든 위치에서 일치 여부를 검사합니다.
-
시간 복잡도: 문자열은 총 \(C^N\)개이고, 각 문자열마다 등장 횟수를 세는 데 \(O(N \cdot |P|)\)가 걸리므로 전체 \(O(C^N \cdot N \cdot |P|)\)입니다. 최대 약 \(6 \times 10^4 \times 50 \approx 3 \times 10^6\)번의 연산으로 여유롭게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll n, c, k;
string p;
ll count_occ(const string &s) {
ll cnt = 0;
for (ll i = 0; i + (ll)p.size() <= (ll)s.size(); i++) {
bool ok = true;
for (ll j = 0; j < (ll)p.size(); j++) {
if (s[i + j] != p[j]) { ok = false; break; }
}
if (ok) cnt++;
}
return cnt;
}
int main() {
fastio
cin >> n >> c >> k;
cin >> p;
string s(n, 'a');
ll total = 1;
for (ll i = 0; i < n; i++) total *= c;
ll ans = 0;
for (ll mask = 0; mask < total; mask++) {
ll cur = mask;
for (ll i = 0; i < n; i++) {
s[i] = 'a' + (cur % c);
cur /= c;
}
if (count_occ(s) == k) ans++;
}
cout << ans % MOD << endl;
return 0;
}
3. [서브태스크 2]: \(N \le 2000\), \(|P| \le 60\), \(K \le 5\)
\(N\)이 최대 \(2000\)까지 커지면 완전 탐색은 불가능하지만, 문자열을 왼쪽부터 한 글자씩 채워 나가는 동적 계획법으로 해결할 수 있습니다. 여기서 등장하는 핵심 도구가 KMP 오토마톤입니다.
문자열을 한 글자씩 이어 붙일 때, 우리가 알아야 할 정보는 "지금까지 만든 문자열의 접미사가 패턴 \(P\)의 접두사와 얼마나 일치하는가"뿐입니다. 이 일치 길이를 상태로 두면, 상태는 \(0\)부터 \(|P|\)까지 총 \(|P|+1\)개입니다. 어떤 상태 \(st\)에서 문자 \(ch\)를 붙였을 때 다음 상태는, KMP의 실패 함수(failure function)를 이용해 미리 계산해 둘 수 있습니다. 일치 길이가 \(|P|\)에 도달하면 패턴이 한 번 등장한 것이며, 이후에도 겹치는 등장을 놓치지 않도록 실패 함수를 따라 적절한 상태로 되돌아갑니다.
-
풀이: 먼저 \(P\)의 실패 함수를 구하고, 각 상태 \(st\)와 각 문자 \(ch\)에 대해 전이 상태
go[st][ch]와 그 전이로 발생하는 등장 횟수 증가량occ[st][ch](전이 결과가 \(|P|\)이면 \(1\), 아니면 \(0\))를 전처리합니다. 이제 \(dp[st][cnt]\)를 "현재 KMP 상태가 \(st\)이고 패턴이 지금까지 \(cnt\)번 등장한 길이 \(L\)짜리 문자열의 개수"로 정의합니다. 글자를 하나 추가할 때마다 모든 상태와 문자에 대해 전이를 적용하여 \(dp\)를 갱신하고, 등장 횟수가 \(K\)를 넘어가는 경우는 흡수 상태(overflow)로 몰아 더 이상 세지 않습니다. \(N\)번 갱신한 뒤, 등장 횟수가 정확히 \(K\)인 모든 상태의 값을 합산합니다. -
시간 복잡도: 한 글자를 추가할 때마다 (상태 수)\(\times\)(등장 횟수 칸)\(\times\)(문자 수) \(= O(|P| \cdot K \cdot C)\)의 전이가 발생하고, 이를 \(N\)번 반복하므로 전체 \(O(N \cdot |P| \cdot K \cdot C)\)입니다. 최대 약 \(2000 \times 61 \times 7 \times 26 \approx 2.2 \times 10^7\)로 충분히 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll n, c, k;
string p;
int main() {
fastio
cin >> n >> c >> k;
cin >> p;
ll m = p.size();
vector<ll> fail(m + 1, 0);
for (ll i = 1; i < m; i++) {
ll j = fail[i];
while (j > 0 && p[i] != p[j]) j = fail[j];
if (p[i] == p[j]) j++;
fail[i + 1] = j;
}
vector<vector<ll>> go(m + 1, vector<ll>(c, 0));
vector<vector<ll>> occ(m + 1, vector<ll>(c, 0));
for (ll st = 0; st <= m; st++) {
for (ll ch = 0; ch < c; ch++) {
ll j = st;
char cc = 'a' + ch;
while (j > 0 && (j == m || p[j] != cc)) j = fail[j];
if (j < m && p[j] == cc) j++;
go[st][ch] = j;
occ[st][ch] = (j == m) ? 1 : 0;
}
}
ll KC = k + 2; // 등장 횟수 0..k+1 (k+1 = 초과 흡수 상태)
vector<vector<ll>> dp(m + 1, vector<ll>(KC, 0));
dp[0][0] = 1;
for (ll step = 0; step < n; step++) {
vector<vector<ll>> ndp(m + 1, vector<ll>(KC, 0));
for (ll st = 0; st <= m; st++) {
for (ll cnt = 0; cnt < KC; cnt++) {
if (!dp[st][cnt]) continue;
ll val = dp[st][cnt];
for (ll ch = 0; ch < c; ch++) {
ll ns = go[st][ch];
ll nc = cnt + occ[st][ch];
if (nc >= KC) nc = KC - 1;
ndp[ns][nc] = (ndp[ns][nc] + val) % MOD;
}
}
}
dp = ndp;
}
ll ans = 0;
for (ll st = 0; st <= m; st++) ans = (ans + dp[st][k]) % MOD;
cout << ans << endl;
return 0;
}
4. [서브태스크 3]: \(N \le 10^9\), \(|P| \le 30\), \(K \le 3\)
\(N\)이 \(10^9\)에 이르면 글자를 하나씩 추가하는 선형 DP는 더 이상 불가능합니다. 그러나 서브태스크 2의 점화식을 자세히 보면, 매 단계의 전이가 상태에 무관하게 동일한 선형 변환임을 알 수 있습니다. 즉, DP 상태 벡터에 매번 같은 행렬을 곱하는 형태이므로, 이 전이를 하나의 행렬로 만들어 행렬 거듭제곱으로 \(N\)번의 갱신을 \(O(\log N)\)번의 행렬 곱셈으로 압축할 수 있습니다.
-
풀이: DP 상태 \((st, cnt)\)를 하나의 인덱스로 펼쳐 길이 \(D = (|P|+1)\cdot(K+1)\)인 벡터로 봅니다. 서브태스크 2의 한 글자 전이를 그대로 행렬 \(T\)로 옮겨, \(T_{(\text{다음 상태})(\text{현재 상태})}\)에 가능한 문자 수만큼 \(1\)을 더합니다. 등장 횟수가 \(K\)를 초과하는 전이는 정답("정확히 \(K\)번")에 절대 기여할 수 없으므로 아예 버립니다(등장 횟수는 단조 증가하므로 한 번 넘어가면 다시 \(K\)가 될 수 없습니다). 초기 상태 벡터는 \((st, cnt) = (0, 0)\)만 \(1\)인 벡터이고, \(T^N\)을 곱한 뒤 등장 횟수가 정확히 \(K\)인 모든 상태의 값을 합산합니다. 이 서브태스크는 \(|P| \le 30\), \(K \le 3\)이라 행렬 크기가 작아(\(D \le 31 \times 4 = 124\)) 여유가 큽니다.
-
시간 복잡도: 행렬 한 변의 길이가 \(D = (|P|+1)(K+1)\)이므로 한 번의 곱셈에 \(O(D^3)\), 거듭제곱에 \(O(D^3 \log N)\)이 걸립니다. 이 서브태스크에서는 \(D \le 124\), \(\log N \approx 30\)으로 매우 빠르게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll n, c, k;
string p;
ll D;
struct Mat {
vector<vector<ll>> a;
Mat() { a.assign(D, vector<ll>(D, 0)); }
};
Mat mul(const Mat &x, const Mat &y) {
Mat r;
for (ll i = 0; i < D; i++) {
for (ll t = 0; t < D; t++) {
if (!x.a[i][t]) continue;
ll v = x.a[i][t];
const vector<ll> &yt = y.a[t];
vector<ll> &ri = r.a[i];
for (ll j = 0; j < D; j++) ri[j] = (ri[j] + v * yt[j]) % MOD;
}
}
return r;
}
int main() {
fastio
cin >> n >> c >> k;
cin >> p;
ll m = p.size();
vector<ll> fail(m + 1, 0);
for (ll i = 1; i < m; i++) {
ll j = fail[i];
while (j > 0 && p[i] != p[j]) j = fail[j];
if (p[i] == p[j]) j++;
fail[i + 1] = j;
}
vector<vector<ll>> go(m + 1, vector<ll>(c, 0));
vector<vector<ll>> occ(m + 1, vector<ll>(c, 0));
for (ll st = 0; st <= m; st++) {
for (ll ch = 0; ch < c; ch++) {
ll j = st;
char cc = 'a' + ch;
while (j > 0 && (j == m || p[j] != cc)) j = fail[j];
if (j < m && p[j] == cc) j++;
go[st][ch] = j;
occ[st][ch] = (j == m) ? 1 : 0;
}
}
ll KC = k + 1; // 등장 횟수 0..k ; k를 넘기는 전이는 버린다
D = (m + 1) * KC;
auto idx = [&](ll st, ll cnt) { return st * KC + cnt; };
Mat T;
for (ll st = 0; st <= m; st++)
for (ll cnt = 0; cnt < KC; cnt++)
for (ll ch = 0; ch < c; ch++) {
ll ns = go[st][ch];
ll nc = cnt + occ[st][ch];
if (nc > k) continue; // k 초과 => "정확히 k"가 될 수 없으므로 제거
T.a[idx(ns, nc)][idx(st, cnt)] = (T.a[idx(ns, nc)][idx(st, cnt)] + 1) % MOD;
}
Mat res; for (ll i = 0; i < D; i++) res.a[i][i] = 1;
ll e = n; Mat base = T;
while (e > 0) {
if (e & 1) res = mul(res, base);
base = mul(base, base);
e >>= 1;
}
ll start = idx(0, 0);
ll ans = 0;
for (ll st = 0; st <= m; st++) ans = (ans + res.a[idx(st, k)][start]) % MOD;
cout << ans << endl;
return 0;
}
5. [서브태스크 4]: 전체 제한 (\(N \le 10^{18}\), \(|P| \le 60\), \(K \le 5\))
서브태스크 3의 행렬 거듭제곱 풀이를 그대로 사용하되, 전체 제한에서는 행렬 크기가 최대 \(D = (60+1)\times(5+1) = 366\)까지 커지고 \(N\)이 \(10^{18}\)이라 \(\log N \approx 60\)입니다. 따라서 행렬 곱셈을 충분히 빠르게 구현하는 것이 관건입니다.
-
풀이: 알고리즘 자체는 서브태스크 3과 동일합니다. 다만 \(D \approx 366\), \(\log N \approx 60\)이므로 곱셈 한 번이 \(366^3 \approx 4.9 \times 10^7\), 거듭제곱 전체로 약 \(5.9 \times 10^9\)번의 곱셈·덧셈이 필요합니다. 이를 시간 안에 통과시키려면 (1) 행렬 곱의 안쪽 두 반복을 \(ikj\) 순서로 두어 캐시 적중률을 높이고, (2) 가운데 원소가 \(0\)이면 안쪽 루프 전체를 건너뛰며, (3) 모든 곱을 64비트로 처리해 매번 모듈러 연산을 하는 식으로 상수를 줄입니다. 위 코드는 이미 이 최적화를 반영하고 있습니다. 등장 횟수가 \(K\)를 넘는 전이를 버려 행렬 차원을 \((|P|+1)(K+1)\)로 유지하는 것도 속도에 직접 기여합니다.
long long입력으로 \(N \le 10^{18}\)을 문제없이 받습니다. -
시간 복잡도: \(O(D^3 \log N)\)이며, \(D = (|P|+1)(K+1) \le 366\), \(\log N \le 60\)입니다. 위 최적화된 구현으로 최악의 경우(약 \(|P|=60\), \(K=5\), \(N=10^{18}\))도 제한 시간 \(5\)초 안에 안정적으로 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll n, c, k;
string p;
ll D;
struct Mat {
vector<vector<ll>> a;
Mat() { a.assign(D, vector<ll>(D, 0)); }
};
Mat mul(const Mat &x, const Mat &y) {
Mat r;
for (ll i = 0; i < D; i++) {
for (ll t = 0; t < D; t++) {
if (!x.a[i][t]) continue;
ll v = x.a[i][t];
const vector<ll> &yt = y.a[t];
vector<ll> &ri = r.a[i];
for (ll j = 0; j < D; j++) ri[j] = (ri[j] + v * yt[j]) % MOD;
}
}
return r;
}
int main() {
fastio
cin >> n >> c >> k;
cin >> p;
ll m = p.size();
vector<ll> fail(m + 1, 0);
for (ll i = 1; i < m; i++) {
ll j = fail[i];
while (j > 0 && p[i] != p[j]) j = fail[j];
if (p[i] == p[j]) j++;
fail[i + 1] = j;
}
vector<vector<ll>> go(m + 1, vector<ll>(c, 0));
vector<vector<ll>> occ(m + 1, vector<ll>(c, 0));
for (ll st = 0; st <= m; st++) {
for (ll ch = 0; ch < c; ch++) {
ll j = st;
char cc = 'a' + ch;
while (j > 0 && (j == m || p[j] != cc)) j = fail[j];
if (j < m && p[j] == cc) j++;
go[st][ch] = j;
occ[st][ch] = (j == m) ? 1 : 0;
}
}
ll KC = k + 1; // 등장 횟수 0..k ; k를 넘기는 전이는 버린다
D = (m + 1) * KC;
auto idx = [&](ll st, ll cnt) { return st * KC + cnt; };
Mat T;
for (ll st = 0; st <= m; st++)
for (ll cnt = 0; cnt < KC; cnt++)
for (ll ch = 0; ch < c; ch++) {
ll ns = go[st][ch];
ll nc = cnt + occ[st][ch];
if (nc > k) continue; // k 초과 => "정확히 k"가 될 수 없으므로 제거
T.a[idx(ns, nc)][idx(st, cnt)] = (T.a[idx(ns, nc)][idx(st, cnt)] + 1) % MOD;
}
Mat res; for (ll i = 0; i < D; i++) res.a[i][i] = 1;
ll e = n; Mat base = T;
while (e > 0) {
if (e & 1) res = mul(res, base);
base = mul(base, base);
e >>= 1;
}
ll start = idx(0, 0);
ll ans = 0;
for (ll st = 0; st <= m; st++) ans = (ans + res.a[idx(st, k)][start]) % MOD;
cout << ans << endl;
return 0;
}
6. 정해
정해는 KMP 오토마톤 위에서의 DP를 행렬 거듭제곱으로 가속하는 풀이입니다. 위 서브태스크 4의 코드가 그대로 정해이며, 여기서는 그 핵심 아이디어를 한 번 더 정리합니다.
6.1. KMP 오토마톤
문자열을 왼쪽부터 한 글자씩 채워 나갈 때, 패턴 \(P\)의 등장을 추적하기 위해 필요한 정보는 "현재까지 만든 문자열의 접미사 중 \(P\)의 접두사와 일치하는 가장 긴 길이"뿐입니다. 이 길이를 상태로 삼으면 상태 집합은 \(\{0, 1, \dots, |P|\}\)로 총 \(|P|+1\)개입니다.
KMP의 실패 함수 \(\text{fail}\)을 이용하면, 상태 \(st\)에서 문자 \(ch\)를 이어 붙였을 때 도달하는 다음 상태를 다음과 같이 결정할 수 있습니다.
$$ \delta(st, ch) = \begin{cases} st + 1 & (st < |P| \text{ 이고 } P[st] = ch) \\ \delta(\text{fail}[st], ch) & (\text{그 외}) \end{cases} $$
전이 결과가 \(|P|\)이면 그 글자를 붙이는 순간 패턴이 한 번 등장한 것입니다. 등장은 겹칠 수 있으므로, 상태 \(|P|\)에서도 실패 함수를 따라 적절한 상태로 되돌아간 뒤 다음 글자 전이를 이어 가면 겹치는 등장까지 모두 셀 수 있습니다(\(P=\texttt{aa}\), \(S=\texttt{aaa}\)에서 등장이 \(2\)번 세지는 이유). 각 상태와 각 문자에 대한 전이 go[st][ch]와 등장 증가량 occ[st][ch]를 미리 계산해 둡니다.
6.2. 등장 횟수 차원과 DP
여기에 "지금까지 패턴이 몇 번 등장했는가"라는 차원을 추가합니다. 우리가 알고 싶은 것은 정확히 \(K\)번이고, \(K\)를 넘어선 순간 그 문자열은 영원히 정답이 될 수 없으므로(등장 횟수는 단조 증가) 등장 횟수는 \(0, 1, \dots, K\)의 \(K+1\)가지만 추적하면 충분합니다.
따라서 DP 상태를 \((st, cnt)\) — KMP 상태 \(st\)와 누적 등장 횟수 \(cnt\) — 로 정의하며, 전체 상태 수는
$$ D = (|P| + 1) \times (K + 1) \le 61 \times 6 = 366 $$
개입니다. 글자를 하나 추가하는 전이는 모든 \((st, cnt)\)에 대해 동일한 규칙을 적용하는 선형 변환이며, \(cnt + \texttt{occ}[st][ch] > K\)가 되는 전이는 버립니다.
6.3. 행렬 거듭제곱
한 글자 전이가 상태 벡터에 대한 고정된 선형 변환이므로, 이를 \(D \times D\) 전이 행렬 \(T\)로 표현하면 길이 \(N\)의 문자열에 대한 결과는 초기 벡터 \(e_{(0,0)}\)에 \(T^N\)을 곱한 것과 같습니다.
$$ \text{ans} = \sum_{st=0}^{|P|} \big(T^N \, e_{(0,0)}\big)_{(st,\,K)} $$
\(T^N\)은 분할 정복(이진 거듭제곱)으로 \(O(D^3 \log N)\)에 계산합니다. \(D \le 366\), \(\log N \le 60\)이며, 행렬 곱셈을 \(ikj\) 순서·영원소 스킵·64비트 누적으로 최적화하면 최악의 경우도 제한 시간 \(5\)초 안에 통과합니다. 모든 연산은 \(1{,}000{,}000{,}007\)로 나눈 나머지로 수행합니다.
평가 및 의견
알파카컵 1회: F - 알파카의 끝없는 울음소리
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카컵 1회: F - 알파카의 끝없는 울음소리