結果
問題 | No.1227 I hate ThREE |
ユーザー |
![]() |
提出日時 | 2020-09-11 22:59:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 1,429 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 95,648 KB |
実行使用メモリ | 50,572 KB |
最終ジャッジ日時 | 2025-01-02 05:43:08 |
合計ジャッジ時間 | 5,473 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}vector<vector<int>> g;ll dp[1001][6006];int C;ll dfs(int now,int d,int par){if(dp[now][d]!=-1) return dp[now][d];dp[now][d]=1;for(auto nex:g[now]) if(nex!=par){ll res=0;if(d+3<=C&&d+3<=6000) res+=dfs(nex,d+3,now);if(d-3>=1) res+=dfs(nex,d-3,now);res%=MOD;dp[now][d]=dp[now][d]*res%MOD;}return dp[now][d];}int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin>>N>>C;g.resize(N);rep(i,N-1){int a,b;cin>>a>>b;a--;b--;g[a].push_back(b);g[b].push_back(a);}for(int i=0;i<N;i++) for(int j=0;j<=6000;j++) dp[i][j]=-1;for(int i=1;i<=min(C,6000);i++) dfs(0,i,-1);if(C<=6000){ll ans=0;for(int k=1;k<=C;k++) ans=(ans+dp[0][k])%MOD;cout<<ans<<"\n";}else{ll ans=0;for(int k=1;k<3000;k++) ans=(ans+dp[0][k])%MOD;ans=ans*2%MOD;ans=(ans+dp[0][3000]*(C-2*2999)%MOD)%MOD;cout<<ans<<"\n";}return 0;}