結果

問題 No.196 典型DP (1)
ユーザー Today03Today03
提出日時 2023-08-07 16:21:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 2,480 bytes
コンパイル時間 2,016 ms
コンパイル使用メモリ 200,544 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-25 10:02:29
合計ジャッジ時間 3,469 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 5 ms
5,376 KB
testcase_20 AC 6 ms
5,376 KB
testcase_21 AC 7 ms
5,376 KB
testcase_22 AC 7 ms
5,376 KB
testcase_23 AC 8 ms
5,376 KB
testcase_24 AC 8 ms
5,376 KB
testcase_25 AC 7 ms
5,376 KB
testcase_26 AC 10 ms
5,376 KB
testcase_27 AC 10 ms
5,376 KB
testcase_28 AC 10 ms
5,376 KB
testcase_29 AC 11 ms
5,376 KB
testcase_30 AC 10 ms
5,376 KB
testcase_31 AC 11 ms
5,376 KB
testcase_32 AC 12 ms
5,376 KB
testcase_33 AC 12 ms
5,376 KB
testcase_34 AC 11 ms
5,376 KB
testcase_35 AC 11 ms
5,376 KB
testcase_36 AC 10 ms
5,376 KB
testcase_37 AC 6 ms
5,376 KB
testcase_38 AC 11 ms
5,376 KB
testcase_39 AC 10 ms
5,376 KB
testcase_40 AC 11 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <unsigned long long MOD>
struct modint {
  unsigned long long value;
  constexpr modint(const unsigned long long x=0) {
    value=x%MOD;
  }
  constexpr modint operator+(const modint other) {
    return modint(*this)+=other;
  }
  constexpr modint operator-(const modint other) {
    return modint(*this)-=other;
  }
  constexpr modint operator*(const modint other) {
    return modint(*this)*=other;
  }
  constexpr modint operator/(const modint other) {
    return modint(*this)/=other;
  }
  constexpr modint &operator+=(const modint other) {
    value+=other.value;
    if (value>=MOD) {
      value-=MOD;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint other) {
    if (value<other.value) {
      value+=MOD;
    }
    value-=other.value;
    return *this;
  }
  constexpr modint &operator*=(const modint other) {
    value=value*other.value%MOD;
    return *this;
  }
  constexpr modint &operator/=(modint other) {
    (*this)*=other.inv();
    return *this;
  }
  constexpr modint pow(long long x) {
    modint ret(1),_this(*this);
    for (;x;x>>=1,_this*=_this) {
      if (x&1) {
        ret*=_this;
      }
    }
    return ret;
  }
  constexpr modint inv() {
    return pow(MOD-2);
  }
  friend ostream& operator<<(ostream& os, const modint &x) {
    return os<<x.value;
  }
  friend istream& operator>>(istream& is, modint &x) {
    is>>x.value;
    x.value%=MOD;
    if (x.value<0) {
      x.value+=MOD;
    }
    return is;
  }
};
using mint=modint<1000000007>;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k;
  cin>>n>>k;
  vector<vector<int>> g(n);
  for (int i=0;i<n-1;i++) {
    int a,b;
    cin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  //a[i]:=部分木のうち、i個の頂点が黒く塗られるような通り数
  auto merge=[&](vector<mint> &a, vector<mint> &b) -> vector<mint> {
    vector<mint> ret(a.size()+b.size()-1);
    for (int i=0;i<a.size();i++) {
      for (int j=0;j<b.size();j++) {
        ret[i+j]+=a[i]*b[j];
      }
    }
    return ret;
  };
  auto dfs=[&](auto&&dfs, int now, int pre) -> vector<mint> {
    //83行目と同じ定義
    //最初は頂点数1から始める
    vector<mint> dp(2);
    dp[0]=1;
    for (int nxt:g[now]) {
      if (nxt!=pre) {
        auto ndp=dfs(dfs,nxt,now);
        dp=merge(dp,ndp);
      }
    }
    dp.back()=1;
    return dp;
  };
  auto dp=dfs(dfs,0,0);
  cout<<dp[k]<<endl;
}
0