QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179696#1222. 多边形hos_lyric#50 163ms44752kbC++146.3kb2023-09-15 01:25:392023-09-15 01:25:39

Judging History

你现在查看的是最新测评结果

  • [2023-09-15 01:25:39]
  • 评测
  • 测评结果:50
  • 用时:163ms
  • 内存:44752kb
  • [2023-09-15 01:25:39]
  • 提交

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<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];
      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 {
    UL[u] = UR[u] = LR[u] = 1;
  }
}
Mint run() {
  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();
 assert(brt==ans);
}
#endif
  }
  return 0;
}

详细

Test #1:

score: 5
Accepted
time: 4ms
memory: 44644kb

input:

5 3
1 1 1 3


output:

2

result:

ok single line: '2'

Test #2:

score: 5
Accepted
time: 4ms
memory: 44648kb

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: 0ms
memory: 44644kb

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: 163ms
memory: 44752kb

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: 1ms
memory: 3752kb

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: 1ms
memory: 3748kb

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: 3752kb

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: 1ms
memory: 3748kb

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: 1ms
memory: 3764kb

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: 3748kb

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: 1ms
memory: 3744kb

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: 1ms
memory: 3840kb

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: 1ms
memory: 3788kb

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: 1ms
memory: 3784kb

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: 3780kb

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: 1ms
memory: 3732kb

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: 1ms
memory: 3788kb

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: 1ms
memory: 3736kb

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: 1ms
memory: 3740kb

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: 1ms
memory: 3740kb

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'