結果

問題 No.196 典型DP (1)
ユーザー Today03Today03
提出日時 2023-08-07 16:21:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 2,480 bytes
コンパイル時間 1,872 ms
コンパイル使用メモリ 198,932 KB
最終ジャッジ日時 2025-02-16 00:00:53
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

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