# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
958689 | adaawf | 힘 센 거북 (IZhO11_turtle) | C++14 | 407 ms | 166908 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int a[25], b[25], c[600005][10], d[600005][10], p[600005][10], ff[1000005];
long long int f[600005][10], g[600005][10], dd[25][25], z;
vector<pair<int, int>> v;
vector<int> vv, va;
long long int power(long long int x, long long int y, long long int mod = z) {
long long int res = 1, h = x;
while (y) {
if (y & 1) res = res * h % mod;
h = h * h % mod;
y >>= 1;
}
return res;
}
long long int C(long long int n, long long int k) {
vector<long long int> res;
for (int i = 0; i < v.size(); i++) {
int h = c[n][i] - c[k][i] - c[n - k][i];
if (h >= v[i].second) {
res.push_back(0);
continue;
}
res.push_back(f[n][i] * g[k][i] % vv[i] * g[n - k][i] % vv[i] * p[h][i] % vv[i]);
}
long long int h = 0;
for (int i = 0; i < v.size(); i++) {
long long int k = z / vv[i];
h = (h + res[i] * k % z * va[i]) % z;
}
return h;
}
bool check(int i, int j) {
if (a[i] > a[j] || b[i] > b[j]) return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, k, t, l;
cin >> n >> m >> k >> t >> z;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
v.push_back({a[i], b[i]});
}
sort(v.begin(), v.end());
for (int i = 1; i <= k; i++) {
a[i] = v[i - 1].first;
b[i] = v[i - 1].second;
}
v.clear();
l = z;
int h = sqrt(z);
for (int i = 2; i <= h; i++) {
if (z % i == 0) {
int c = 0;
while (z % i == 0) {
c++;
z /= i;
}
v.push_back({i, c});
int h = power(i, c, l);
if (h == 0) h = l;
vv.push_back(h);
}
}
if (z != 1) v.push_back({z, 1}), vv.push_back(z);
z = l;
for (int i = 1; i <= n + m; i++) {
for (int j = 0; j < v.size(); j++) {
long long int h = v[j].first;
while (h <= i) {
c[i][j] += i / h;
h *= v[j].first;
}
int k = i;
while (k % v[j].first == 0) {
k /= v[j].first;
}
d[i][j] = k;
}
}
for (int j = 0; j < v.size(); j++) {
va.push_back(power(z / vv[j], vv[j] - 2, vv[j]));
f[0][j] = 1;
for (int i = 1; i <= n + m; i++) {
f[i][j] = f[i - 1][j] * d[i][j] % vv[j];
}
g[n + m][j] = power(f[n + m][j], vv[j] - 2, vv[j]);
for (int i = n + m - 1; i >= 0; i--) {
g[i][j] = g[i + 1][j] * d[i + 1][j] % vv[j];
}
p[0][j] = 1;
for (int i = 1; i <= n + m; i++) {
p[i][j] = 1ll * p[i - 1][j] * v[j].first % vv[j];
}
}
a[k + 1] = n, b[k + 1] = m;
k++;
for (int i = 0; i < k; i++) {
if (!check(i, i + 1)) continue;
dd[i][i + 1] = C(a[i + 1] - a[i] + b[i + 1] - b[i], a[i + 1] - a[i]);
}
for (int d = 3; d <= k + 1; d++) {
for (int i = 0; i <= k - d + 1; i++) {
int j = i + d - 1;
if (!check(i, j)) continue;
dd[i][j] = C(a[j] - a[i] + b[j] - b[i], a[j] - a[i]);
for (int l = i + 1; l < j; l++) {
if (!check(i, l)) continue;
dd[i][j] = (dd[i][j] + z - C(a[l] - a[i] + b[l] - b[i], a[l] - a[i]) * dd[l][j] % z) % z;
}
}
}
long long int res = 0;
for (int i = 0; i < (1 << (k + 1)); i++) {
int h = __builtin_popcount(i);
if (h > t + 2) continue;
if (!(i & 1) || !(i & (1 << k))) continue;
vector<int> v;
long long int c = 1;
for (int j = 0; j <= k; j++) {
if (i & (1 << j)) {
v.push_back(j);
}
}
for (int i = 1; i < v.size(); i++) {
c *= dd[v[i - 1]][v[i]];
c %= z;
}
res = (res + c) % z;
}
cout << res;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |