QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179701 | #1222. 多边形 | hos_lyric# | 50 | 147ms | 44820kb | C++14 | 6.5kb | 2023-09-15 01:44:51 | 2023-09-15 01:44:52 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
int N, K;
vector<int> P;
vector<vector<int>> graph;
namespace brute {
vector<int> ls;
void dfs(int u) {
if (!graph[u].empty()) {
for (const int v : graph[u]) {
dfs(v);
}
} else {
ls.push_back(u);
}
}
bool adj[20][20];
void ae(int u, int v) {
adj[u][v] = adj[v][u] = true;
}
Mint dp[1 << 19][20];
Mint run() {
if (N <= 2) {
return 0;
}
ls.clear();
dfs(0);
memset(adj, 0, sizeof(adj));
for (int u = 1; u < N; ++u) {
ae(P[u], u);
}
const int lsLen = ls.size();
for (int j = 0; j < lsLen; ++j) for (int k = 1; k <= K; ++k) {
ae(ls[j], ls[(j + k) % lsLen]);
}
memset(dp, 0, sizeof(dp));
dp[0][N - 1] = 1;
for (int p = 0; p < 1 << (N - 1); ++p) {
for (int u = 0; u < N; ++u) if (dp[p][u]) {
for (int v = 0; v < N - 1; ++v) if (!(p & 1 << v) && adj[u][v]) {
dp[p | 1 << v][v] += dp[p][u];
}
}
}
Mint ans = 0;
for (int u = 0; u < N; ++u) if (adj[N - 1][u]) {
ans += dp[(1 << (N - 1)) - 1][u];
}
ans /= 2;
return ans;
}
} // brute
namespace k1 {
vector<int> ls;
vector<Mint> UL, UR, LR;
Mint ans;
void dfs(int u) {
const int deg = graph[u].size();
if (deg) {
for (const int v : graph[u]) {
dfs(v);
}
vector<Mint> pre(deg + 1), suf(deg + 1);
pre[0] = 1;
for (int j = 0; j < deg; ++j) pre[j + 1] = pre[j] * LR[graph[u][j]];
suf[deg] = 1;
for (int j = deg; --j >= 0; ) suf[j] = LR[graph[u][j]] * suf[j + 1];
UL[u] = pre[deg - 1] * UL[graph[u][deg - 1]];
UR[u] = UR[graph[u][0]] * suf[1];
for (int j = 0; j < deg - 1; ++j) {
LR[u] += pre[j] * UL[graph[u][j]] * UR[graph[u][j + 1]] * suf[j + 2];
}
if (u == 0 && deg >= 2) {
ans += LR[0];
if (ls.size() >= 3) {
Mint prod = 1;
prod *= UR[graph[u][0]];
for (int j = 1; j < deg - 1; ++j) prod *= LR[graph[u][j]];
prod *= UL[graph[u][deg - 1]];
ans += prod;
}
}
} else {
ls.push_back(u);
UL[u] = UR[u] = LR[u] = 1;
}
}
Mint run() {
ls.clear();
UL.assign(N, 0);
UR.assign(N, 0);
LR.assign(N, 0);
ans = 0;
dfs(0);
return ans;
}
} // k1
int main() {
for (; ~scanf("%d%d", &N, &K); ) {
P.assign(N, -1);
for (int u = 1; u < N; ++u) {
scanf("%d", &P[u]);
--P[u];
}
graph.assign(N, {});
for (int u = 1; u < N; ++u) {
graph[P[u]].push_back(u);
}
Mint ans = 0;
if (K == 1) {
ans = k1::run();
} else if (N <= 20) {
ans = brute::run();
}
printf("%u\n", ans.x);
#ifdef LOCAL
if(N<=20){
const Mint brt=brute::run();
if(brt!=ans)cerr<<N<<" "<<K<<" "<<P<<": "<<brt<<" "<<ans<<endl;
assert(brt==ans);
}
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 4ms
memory: 44776kb
input:
5 3 1 1 1 3
output:
2
result:
ok single line: '2'
Test #2:
score: 5
Accepted
time: 3ms
memory: 44760kb
input:
10 3 1 2 3 4 5 2 5 4 1
output:
16
result:
ok single line: '16'
Test #3:
score: 5
Accepted
time: 6ms
memory: 44744kb
input:
15 3 1 1 2 1 1 1 3 3 1 1 1 1 1 1
output:
23854
result:
ok single line: '23854'
Test #4:
score: 5
Accepted
time: 147ms
memory: 44820kb
input:
20 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 18 18
output:
24097065
result:
ok single line: '24097065'
Test #5:
score: 5
Accepted
time: 0ms
memory: 3928kb
input:
1000 1 1 2 3 4 5 6 7 8 7 10 11 10 6 14 15 16 17 18 19 19 21 18 23 23 17 26 27 26 29 30 30 32 29 16 35 36 35 15 39 39 41 41 43 43 14 46 46 48 49 48 5 52 53 54 53 56 56 58 58 52 61 62 63 63 65 66 67 66 69 69 71 71 65 74 62 76 76 78 79 79 81 78 83 83 85 85 87 61 89 90 89 92 92 4 95 96 97 98 98 97 96 10...
output:
0
result:
ok single line: '0'
Test #6:
score: 5
Accepted
time: 0ms
memory: 4176kb
input:
999 1 1 2 3 4 5 6 7 8 9 10 10 9 13 13 8 7 17 18 19 20 21 22 22 21 20 26 26 19 29 30 30 32 32 29 35 35 37 38 38 37 18 42 43 43 42 46 46 17 49 50 50 49 53 54 54 53 6 58 59 60 61 62 63 63 65 65 62 61 60 70 70 72 72 59 75 76 77 77 76 75 81 81 58 84 85 86 86 88 89 90 90 92 92 89 88 96 97 97 96 100 100 85...
output:
2
result:
ok single line: '2'
Test #7:
score: 5
Accepted
time: 0ms
memory: 4136kb
input:
1000 1 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 16 17 17 19 19 21 21 16 24 24 11 10 28 29 29 28 32 33 34 34 33 37 37 32 40 40 9 43 43 8 46 46 7 49 50 50 49 53 53 55 55 6 58 59 60 61 61 63 63 60 59 67 68 69 69 68 67 73 74 74 76 76 78 78 73 58 82 83 83 85 85 82 88 89 89 88 92 92 94 94 96 96 5 99 100 100 10...
output:
1
result:
ok single line: '1'
Test #8:
score: 5
Accepted
time: 0ms
memory: 3952kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
106890205
result:
ok single line: '106890205'
Test #9:
score: 5
Accepted
time: 0ms
memory: 3868kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 1 3 2 4 6 3 1 2 3 7 1 6 7 1 4 2 2 6 4 7 7 1 48 48 48 49 49 49 50 50 50 51 51 51 52 52 52 53 53 53 54 54 54 55 55 55 56 56 56 57 57 57 58 58 58 59 59 59 60 60 60 61 61 61 62 62 62 63 63 63 64 64 64 65 65 65 66 66 66 67 67 67 68 68 68 69 69 69 7...
output:
420850835
result:
ok single line: '420850835'
Test #10:
score: 5
Accepted
time: 0ms
memory: 3876kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
570335790
result:
ok single line: '570335790'
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
input:
1000 2 1 2 3 4 5 6 7 8 8 7 6 12 12 5 15 4 17 18 19 20 21 22 23 22 25 26 26 28 28 30 30 25 21 34 35 36 36 35 39 39 41 41 34 44 45 45 47 44 20 50 51 52 53 52 51 56 57 57 56 50 61 62 63 64 65 65 67 67 69 64 71 72 73 74 75 75 74 73 72 80 80 82 63 84 84 86 86 62 89 90 90 89 93 94 95 95 97 94 99 99 93 102...
output:
0
result:
wrong answer 1st lines differ - expected: '178991712', found: '0'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
1000 2 1 2 3 4 5 6 7 8 9 9 11 8 13 13 7 16 17 16 19 19 21 6 5 24 25 25 27 24 29 29 31 4 33 34 35 36 36 35 39 34 41 42 42 41 33 46 47 48 48 47 46 3 53 54 55 56 55 58 58 54 53 62 63 62 65 65 67 2 69 70 71 72 72 74 71 76 77 77 79 79 76 70 83 84 85 86 87 88 89 90 90 92 93 94 93 92 89 98 99 99 98 102 103...
output:
0
result:
wrong answer 1st lines differ - expected: '460227781', found: '0'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 3860kb
input:
1000 2 1 2 3 4 5 6 7 8 7 6 11 5 13 13 15 15 17 17 4 20 20 22 23 24 25 26 26 25 24 30 23 32 22 34 35 36 37 38 38 37 36 42 43 44 44 46 43 48 48 50 50 42 53 54 55 55 57 58 58 57 61 61 54 53 65 65 67 67 35 70 71 70 34 74 75 76 77 78 78 77 81 82 82 84 84 81 76 88 89 88 91 92 93 93 92 91 97 98 97 100 100 ...
output:
0
result:
wrong answer 1st lines differ - expected: '125424813', found: '0'
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3844kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
0
result:
wrong answer 1st lines differ - expected: '23756983', found: '0'
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 3844kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 3 4 19 11 19 15 10 1 3 21 10 9 17 20 5 12 16 7 12 12 11 2 4 7 4 20 3 21 2 4 16 2 11 16 16 8 4 15 14 12 1 6 7 11 19 8 1 6 2 2 ...
output:
0
result:
wrong answer 1st lines differ - expected: '325532742', found: '0'
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 4152kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
0
result:
wrong answer 1st lines differ - expected: '116800683', found: '0'
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
input:
1000 3 1 2 3 4 5 6 5 8 9 10 11 12 12 11 15 10 17 18 17 20 21 22 21 20 9 26 27 28 28 27 26 32 32 34 8 36 36 38 39 40 40 39 43 43 45 38 47 48 48 47 4 52 52 54 54 3 57 58 59 60 61 61 60 64 59 66 67 67 69 66 71 72 73 72 71 76 77 77 76 58 81 82 83 83 82 86 87 88 89 88 91 92 92 91 95 95 87 98 86 100 100 1...
output:
0
result:
wrong answer 1st lines differ - expected: '767516039', found: '0'
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 3960kb
input:
1000 3 1 2 3 4 5 6 7 7 6 10 11 12 10 5 15 15 4 18 19 20 21 22 22 21 25 26 26 25 29 20 31 32 32 34 34 31 37 19 39 39 18 42 43 44 45 46 45 48 48 50 44 52 52 54 43 56 57 58 59 59 61 62 62 61 58 66 67 67 66 57 71 72 72 71 56 76 77 78 77 76 81 81 42 84 85 86 86 85 89 90 89 92 93 92 84 96 3 98 99 100 101 ...
output:
0
result:
wrong answer 1st lines differ - expected: '776061489', found: '0'
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 3936kb
input:
1000 3 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
0
result:
wrong answer 1st lines differ - expected: '357633930', found: '0'
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 3928kb
input:
1000 3 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
0
result:
wrong answer 1st lines differ - expected: '568729964', found: '0'