結果
| 問題 | No.1227 I hate ThREE |
| ユーザー |
 ziita
|
| 提出日時 | 2021-04-25 22:03:19 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,923 bytes |
| コンパイル時間 | 21,577 ms |
| コンパイル使用メモリ | 389,876 KB |
| 実行使用メモリ | 41,472 KB |
| 最終ジャッジ日時 | 2024-07-04 09:36:22 |
| 合計ジャッジ時間 | 21,966 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,944 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 60 ms
40,448 KB |
| testcase_04 | AC | 60 ms
40,832 KB |
| testcase_05 | AC | 57 ms
39,168 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
ソースコード
#![allow(unused_imports)]
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::ops::*;
// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254 より
macro_rules! eprint {
($($t:tt)*) => {{
use ::std::io::Write;
let _ = write!(::std::io::stderr(), $($t)*);
}};
}
macro_rules! eprintln {
() => { eprintln!(""); };
($($t:tt)*) => {{
use ::std::io::Write;
let _ = writeln!(::std::io::stderr(), $($t)*);
}};
}
macro_rules! dbg {
($v:expr) => {{
let val = $v;
eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
val
}}
}
macro_rules! mat {
($($e:expr),*) => { Vec::from(vec![$($e),*]) };
($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}
macro_rules! ok {
($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
$a$([$i])*.$f($($t),*)
};
($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
let t = $e;
ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
} };
}
pub fn readln() -> String {
let mut line = String::new();
::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
line
}
macro_rules! read {
($($t:tt),*; $n:expr) => {{
let stdin = ::std::io::stdin();
let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
let line = line.unwrap();
let mut it = line.split_whitespace();
_read!(it; $($t),*)
}).collect::<Vec<_>>();
ret
}};
($($t:tt),*) => {{
let line = readln();
let mut it = line.split_whitespace();
_read!(it; $($t),*)
}};
}
macro_rules! _read {
($it:ident; [char]) => {
_read!($it; String).chars().collect::<Vec<_>>()
};
($it:ident; [u8]) => {
Vec::from(_read!($it; String).into_bytes())
};
($it:ident; usize1) => {
$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
};
($it:ident; [usize1]) => {
$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
};
($it:ident; [$t:ty]) => {
$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
};
($it:ident; $t:ty) => {
$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
};
($it:ident; $($t:tt),+) => {
($(_read!($it; $t)),*)
};
}
pub fn main() {
let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}
// const MOD: usize = 998244353;
// const MOD: usize = 1_000_000_007;
const INF: i64 = std::i64::MAX/100;
// https://yukicoder.me/submissions/585145 より
// ---------- begin ModInt ----------
mod modint {
#[allow(dead_code)]
pub struct Mod;
impl ConstantModulo for Mod {
const MOD: u32 = 1_000_000_007;
}
#[allow(dead_code)]
pub struct StaticMod;
static mut STATIC_MOD: u32 = 0;
impl Modulo for StaticMod {
fn modulo() -> u32 {
unsafe { STATIC_MOD }
}
}
#[allow(dead_code)]
impl StaticMod {
pub fn set_modulo(p: u32) {
unsafe {
STATIC_MOD = p;
}
}
}
use std::marker::*;
use std::ops::*;
pub trait Modulo {
fn modulo() -> u32;
}
pub trait ConstantModulo {
const MOD: u32;
}
impl<T> Modulo for T
where
T: ConstantModulo,
{
fn modulo() -> u32 {
T::MOD
}
}
pub struct ModInt<T>(pub u32, PhantomData<T>);
impl<T> Clone for ModInt<T> {
fn clone(&self) -> Self {
ModInt::new_unchecked(self.0)
}
}
impl<T> Copy for ModInt<T> {}
impl<T: Modulo> Add for ModInt<T> {
type Output = ModInt<T>;
fn add(self, rhs: Self) -> Self::Output {
let mut d = self.0 + rhs.0;
if d >= T::modulo() {
d -= T::modulo();
}
ModInt::new_unchecked(d)
}
}
impl<T: Modulo> AddAssign for ModInt<T> {
fn add_assign(&mut self, rhs: Self) {
*self = *self + rhs;
}
}
impl<T: Modulo> Sub for ModInt<T> {
type Output = ModInt<T>;
fn sub(self, rhs: Self) -> Self::Output {
let mut d = T::modulo() + self.0 - rhs.0;
if d >= T::modulo() {
d -= T::modulo();
}
ModInt::new_unchecked(d)
}
}
impl<T: Modulo> SubAssign for ModInt<T> {
fn sub_assign(&mut self, rhs: Self) {
*self = *self - rhs;
}
}
impl<T: Modulo> Mul for ModInt<T> {
type Output = ModInt<T>;
fn mul(self, rhs: Self) -> Self::Output {
let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;
ModInt::new_unchecked(v as u32)
}
}
impl<T: Modulo> MulAssign for ModInt<T> {
fn mul_assign(&mut self, rhs: Self) {
*self = *self * rhs;
}
}
impl<T: Modulo> Neg for ModInt<T> {
type Output = ModInt<T>;
fn neg(self) -> Self::Output {
if self.0 == 0 {
Self::zero()
} else {
Self::new_unchecked(T::modulo() - self.0)
}
}
}
impl<T> std::fmt::Display for ModInt<T> {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl<T: Modulo> std::str::FromStr for ModInt<T> {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let val = s.parse::<u32>()?;
Ok(ModInt::new(val))
}
}
impl<T: Modulo> From<usize> for ModInt<T> {
fn from(val: usize) -> ModInt<T> {
ModInt::new_unchecked((val % T::modulo() as usize) as u32)
}
}
impl<T: Modulo> From<u64> for ModInt<T> {
fn from(val: u64) -> ModInt<T> {
ModInt::new_unchecked((val % T::modulo() as u64) as u32)
}
}
impl<T: Modulo> From<i64> for ModInt<T> {
fn from(val: i64) -> ModInt<T> {
let m = T::modulo() as i64;
ModInt::new((val % m + m) as u32)
}
}
#[allow(dead_code)]
impl<T> ModInt<T> {
pub fn new_unchecked(d: u32) -> Self {
ModInt(d, PhantomData)
}
pub fn zero() -> Self {
ModInt::new_unchecked(0)
}
pub fn one() -> Self {
ModInt::new_unchecked(1)
}
pub fn is_zero(&self) -> bool {
self.0 == 0
}
}
#[allow(dead_code)]
impl<T: Modulo> ModInt<T> {
pub fn new(d: u32) -> Self {
ModInt::new_unchecked(d % T::modulo())
}
pub fn pow(&self, mut n: u64) -> Self {
let mut t = Self::one();
let mut s = *self;
while n > 0 {
if n & 1 == 1 {
t *= s;
}
s *= s;
n >>= 1;
}
t
}
pub fn inv(&self) -> Self {
assert!(self.0 != 0);
self.pow(T::modulo() as u64 - 2)
}
}
#[allow(dead_code)]
pub fn mod_pow(r: u64, mut n: u64, m: u64) -> u64 {
let mut t = 1 % m;
let mut s = r % m;
while n > 0 {
if n & 1 == 1 {
t = t * s % m;
}
s = s * s % m;
n >>= 1;
}
t
}
}
// ---------- end ModInt ----------
// ---------- begin Precalc ----------
mod precalc {
use super::modint::*;
#[allow(dead_code)]
pub struct Precalc<T> {
inv: Vec<ModInt<T>>,
fact: Vec<ModInt<T>>,
ifact: Vec<ModInt<T>>,
}
#[allow(dead_code)]
impl<T: Modulo> Precalc<T> {
pub fn new(n: usize) -> Precalc<T> {
let mut inv = vec![ModInt::one(); n + 1];
let mut fact = vec![ModInt::one(); n + 1];
let mut ifact = vec![ModInt::one(); n + 1];
for i in 2..(n + 1) {
fact[i] = fact[i - 1] * ModInt::new_unchecked(i as u32);
}
ifact[n] = fact[n].inv();
if n > 0 {
inv[n] = ifact[n] * fact[n - 1];
}
for i in (1..n).rev() {
ifact[i] = ifact[i + 1] * ModInt::new_unchecked((i + 1) as u32);
inv[i] = ifact[i] * fact[i - 1];
}
Precalc {
inv: inv,
fact: fact,
ifact: ifact,
}
}
pub fn inv(&self, n: usize) -> ModInt<T> {
assert!(n > 0);
self.inv[n]
}
pub fn fact(&self, n: usize) -> ModInt<T> {
self.fact[n]
}
pub fn ifact(&self, n: usize) -> ModInt<T> {
self.ifact[n]
}
pub fn perm(&self, n: usize, k: usize) -> ModInt<T> {
if k > n {
return ModInt::zero();
}
self.fact[n] * self.ifact[n - k]
}
pub fn comb(&self, n: usize, k: usize) -> ModInt<T> {
if k > n {
return ModInt::zero();
}
self.fact[n] * self.ifact[k] * self.ifact[n - k]
}
}
}
// ---------- end Precalc ----------
use modint::*;
type M = ModInt<Mod>;
fn solve() {
let (n,c) = read!(usize,usize);
let ab = read!(usize,usize;n-1);
let mut edge = vec![vec![];n];
for &(a,b) in &ab {
edge[a-1].push(b-1);
edge[b-1].push(a-1);
}
let mut dp = vec![vec![M::one();10000];n];
dfs(0,n,c,&edge,&mut dp);
let mut ans = M::zero();
let l = min(1+5000,c);
let r = max(c as i64 -5000,l as i64+1) as usize;
for i in 1..=l {
ans += dp[0][i];
}
ans += M::new(2).pow((n-1) as u64) * M::from(r-l-1);
for i in r..=c {
ans += dp[0][c-i];
}
println!("{}",ans);
}
fn dfs(cur: usize, p: usize, c: usize, edge: &Vec<Vec<usize>>, mut dp: &mut Vec<Vec<M>>) {
for &e in &edge[cur] {
if p==e {
continue;
}
dfs(e,cur,c,&edge,&mut dp);
for i in 0..9000 {
let mut count = M::zero();
if i+3<=c {
count += dp[e][i+3];
}
if i>=4 && i-3<=c {
count += dp[e][i-3];
}
dp[cur][i] *= count;
}
}
}
fn run() {
let stack_size = 104_857_600; // 100 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
solve();
}