Advertisement
ivnikkk

Untitled

Jan 28th, 2023
609
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. const int mod = 1e9 + 7;
  6. const int inv2 = 500000004;
  7. struct Mint {
  8.     int z;
  9.     Mint() : z(0) {}
  10.     Mint(int _z) : z(_z) {}
  11.     Mint operator-(const Mint& other) const {
  12.         int val = z - other.z + mod;
  13.         if (val >= mod) { val -= mod; }
  14.         return Mint(val);
  15.     }
  16.     Mint operator-(const int& other) const {
  17.         int val = z - other + mod;
  18.         if (val >= mod) { val -= mod; }
  19.         return Mint(val);
  20.     }
  21.     Mint operator+(const Mint& other) const {
  22.         int val = z + other.z;
  23.         if (val >= mod) { val -= mod; }
  24.         return Mint(val);
  25.     }
  26.     Mint operator+(const int& other) const {
  27.         int val = z + other;
  28.         if (val >= mod) { val -= mod; }
  29.         return Mint(val);
  30.     }
  31.     Mint operator*(const Mint& other) const {
  32.         int val = (1ll * z * other.z) % mod;
  33.         return Mint(val);
  34.     }
  35.     Mint operator*(const int& other) const {
  36.         int val = (1ll * z * other) % mod;
  37.         return Mint(val);
  38.     }
  39. };
  40. int k;
  41. vector<vector<int>> gr;
  42. vector<Mint> dp[2];
  43. void dfs(int v, int p) {
  44.     vector<Mint> dp2[2];
  45.     for (int _ = 0; _ <= 1; _++) {
  46.         dp2[_].resize(k + 1);
  47.     }
  48.     dp2[0][0] = Mint(1);
  49.     dp[0][v] = 1;
  50.     int ind = 1;
  51.     for (int& u : gr[v]) {
  52.         if (u == p) {
  53.             continue;
  54.         }
  55.         dfs(u, v);
  56.         dp[0][v] = (dp[0][v] * (dp[1][u] + dp[0][u]));
  57.         for (int i = 0; i <= k; i++) {
  58.             dp2[ind][i] = (dp2[ind ^ 1][i] * (dp[0][u] + dp[1][u]));
  59.             if (i) {
  60.                 dp2[ind][i] = (dp2[ind][i] + (dp2[ind ^ 1][i - 1] * dp[0][u]));
  61.             }
  62.         }
  63.         dp2[ind ^ 1] = dp2[ind];
  64.         ind ^= 1;
  65.     }
  66.     for (int i = 2; i <= k - 1; i++) {
  67.         dp[1][v] = dp[1][v] + dp2[ind][i];
  68.     }
  69. }
  70. signed main() {
  71. #ifdef _DEBUG
  72.     freopen("input.txt", "r", stdin);
  73.     freopen("output.txt", "w", stdout);
  74. #endif
  75.     ios_base::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.     int n; cin >> n >> k;
  78.     gr.resize(n);
  79.     dp[0].resize(n, Mint());
  80.     dp[1].resize(n, Mint());
  81.     for (int u = 1; u < n; u++) {
  82.         int v; cin >> v; v--;
  83.         gr[v].push_back(u);
  84.     }
  85.     dfs(0, 0);
  86.     cout << (dp[0][0] + dp[1][0]).z;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement