結果
| 問題 |
No.196 典型DP (1)
|
| コンテスト | |
| ユーザー |
 へのく
|
| 提出日時 | 2021-07-16 15:59:25 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 26 ms / 2,000 ms |
| コード長 | 23,862 bytes |
| コンパイル時間 | 14,417 ms |
| コンパイル使用メモリ | 394,692 KB |
| 実行使用メモリ | 18,304 KB |
| 最終ジャッジ日時 | 2024-07-06 03:00:57 |
| 合計ジャッジ時間 | 15,179 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 41 |
ソースコード
#![allow(non_snake_case)]
use crate::modulo::F;
#[allow(unused_imports)]
use crate::{arraylist::List, scanner::Scanner};
fn main() {
let ret = calc();
println!("{}", ret);
}
fn calc() -> F {
let mut scan = Scanner::new();
let n = scan.int();
let k = scan.int();
let mut g = list![list![];n];
for _ in 0..n - 1 {
let a = scan.int();
let b = scan.int();
g[a].push(b);
g[b].push(a);
}
let mut e = E {
n,
g,
dp: list![F::zero();n;n+1],
size: list![0;n],
};
e.dfs(0, -1);
e.dp[0][k]
}
struct E {
n: isize,
g: List<List<isize>>,
dp: List<List<F>>,
size: List<isize>,
}
impl E {
fn dfs(&mut self, curr: isize, prev: isize) {
self.dp[curr][0] = F::one();
self.size[curr] = 1;
for next in self.g[curr].clone() {
if next == prev {
continue;
}
self.dfs(next, curr);
self.merge(curr, next);
tmp![(self.size[curr]) += self.size[next]];
}
self.dp[curr][self.size[curr]] = F::one();
}
fn merge(&mut self, a: isize, b: isize) {
let mut ret = list![F::zero();self.n+1];
for i in 0..=self.size[a] {
for j in 0..=self.size[b] {
tmp![(ret[i + j]) += self.dp[a][i] * self.dp[b][j]];
}
}
self.dp[a] = ret;
}
}
pub mod modulo {
use crate::nums::inv_gcd;
use crate::{
impl_num_functions,
independent::integer::{Int, Num},
};
use std::cell::RefCell;
use std::fmt::Debug;
use std::marker::PhantomData;
use std::ops::*;
use std::sync::atomic::{self, AtomicU32};
use std::thread::LocalKey;
pub trait Modulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord {
const M: u32;
const HINT_M_IS_PRIME: bool;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
}
pub trait DynamicModulus:
'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord
{
fn state() -> &'static AtomicU32 {
static M: AtomicU32 = AtomicU32::new(1_000_000_007);
&M
}
fn update(m: u32) {
Self::state().store(m, atomic::Ordering::SeqCst)
}
fn umod() -> u32 {
Self::state().load(atomic::Ordering::SeqCst)
}
}
#[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub enum DefaultId {}
impl DynamicModulus for DefaultId {}
macro_rules! impl_from_for_modint {
($name:ident, $guard: ident, $($tpe:ident),*) => {
$(
impl<T: $guard> From<$tpe> for $name<T> {
fn from(n: $tpe) -> Self {
Self::new(n)
}
}
)*
};
}
macro_rules! impl_assign {
($name:ident, $guard:ident, $($t1:ty, $t2:ty, $fa:ident, $f:ident),*) => {
$(
impl<T: $guard> $t1 for $name<T> {
type Output = Self;
#[inline]
fn $f(self, other: Self) -> Self {
<Self as ModInt>::$f(self, other)
}
}
impl<T: $guard> $t2 for $name<T> {
#[inline]
fn $fa(&mut self, other: Self) {
*self = <Self as ModInt>::$f(*self, other);
}
}
)*
};
}
macro_rules! impl_modint_structs {
($name:ident, $guard:ident) => {
#[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
#[repr(transparent)]
pub struct $name<T> {
pub val: u32,
phantom: PhantomData<fn() -> T>,
}
impl<T> Debug for $name<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.val.fmt(f)
}
}
impl<T: $guard> $name<T> {
#[inline]
pub fn new<U: Int>(a: U) -> Self {
<Self as ModInt>::new(a)
}
#[inline]
pub fn inv(self) -> Self {
<Self as ModInt>::inv(self)
}
#[inline]
pub fn raw(val: u32) -> Self {
Self {
val,
phantom: PhantomData,
}
}
#[inline]
pub fn pow<U: Int>(self, x: U) -> Self {
<Self as ModInt>::pow(self, x)
}
#[inline]
pub fn zero() -> Self {
<Self as Num>::zero()
}
#[inline]
pub fn one() -> Self {
<Self as Num>::one()
}
}
impl<T: $guard> Default for $name<T> {
fn default() -> Self {
Self::zero()
}
}
impl<T> std::fmt::Display for $name<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl_from_for_modint!(
$name, $guard, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize
);
impl_assign!(
$name, $guard, Add, AddAssign, add_assign, add, Sub, SubAssign, sub_assign, sub,
Mul, MulAssign, mul_assign, mul, Div, DivAssign, div_assign, div, Rem, RemAssign,
rem_assign, rem
);
impl<T: $guard> Num for $name<T> {
impl_num_functions!(|s: &Self| s.val, |x| Self::new(x as i128), |s: Self| if s
< Self::zero()
{
-1
} else if s > Self::zero() {
1
} else {
0
});
}
impl<T: $guard> Int for $name<T> {
fn powint(&self, n: i64) -> Self {
self.pow(n)
}
fn cmul(&self, b: Self) -> Option<Self> {
Some(*self * b)
}
}
};
}
impl_modint_structs!(StaticModInt, Modulus);
impl_modint_structs!(DynamicModInt, DynamicModulus);
#[macro_export]
macro_rules! modint {
($name:ident) => {
$crate::modint!($name, $name, true);
};
($value:expr, $name:ident, $is_prime:literal) => {
#[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub enum $name {}
impl $crate::modulo::Modulus for $name {
const M: u32 = $value as _;
const HINT_M_IS_PRIME: bool = $is_prime;
fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<$name>>> = ::std::default::Default::default();
}
&BUTTERFLY_CACHE
}
}
};
}
#[allow(non_upper_case_globals)]
const F1e9_7: u32 = 1000000007;
modint!(F1e9_7);
pub type F = StaticModInt<F1e9_7>;
const F998244353: u32 = 998244353;
modint!(F998244353);
pub type D = DynamicModInt<DefaultId>;
pub trait ModInt: Int {
fn new<U: Int>(val: U) -> Self {
let x = val.to_i128();
Self::raw(x.rem_euclid(Self::modulus() as i128) as _)
}
fn inv(self) -> Self {
if Self::mod_is_prime() {
Self::pow(self, Self::modulus() - 2)
} else {
let (g, x) = inv_gcd(Self::val(self) as _, Self::modulus() as _);
if g != 1 {
panic!("the multiplicative inverse does not exist");
} else {
Self::new(x)
}
}
}
fn raw(val: u32) -> Self;
fn val(self) -> u32;
fn modulus() -> u32;
fn mod_is_prime() -> bool;
fn add(self, other: Self) -> Self {
let mut ret = self.val() + other.val();
if ret >= Self::modulus() {
ret -= Self::modulus();
}
Self::raw(ret)
}
fn sub(self, other: Self) -> Self {
let mut ret = self.val().wrapping_sub(other.val());
if ret >= Self::modulus() {
ret = ret.wrapping_add(Self::modulus());
}
Self::raw(ret)
}
fn mul(self, other: Self) -> Self {
Self::raw(
(u64::from(self.val()) * u64::from(other.val()) % u64::from(Self::modulus())) as _,
)
}
fn div(self, other: Self) -> Self {
self * other.inv()
}
fn rem(self, other: Self) -> Self {
Self::raw(self.val() % other.val())
}
fn pow<U: Int>(self, x: U) -> Self {
let mut n = x.to_i64();
let mut a = self;
let mut res = Self::raw(1);
while n > 0 {
if n & 1 == 1 {
res *= a;
}
a = a * a;
n >>= 1;
}
res
}
}
impl<M: Modulus> ModInt for StaticModInt<M> {
fn raw(val: u32) -> Self {
Self::raw(val)
}
fn val(self) -> u32 {
self.val
}
fn modulus() -> u32 {
M::M
}
fn mod_is_prime() -> bool {
M::HINT_M_IS_PRIME
}
}
impl<M: DynamicModulus> ModInt for DynamicModInt<M> {
fn raw(val: u32) -> Self {
Self::raw(val)
}
fn val(self) -> u32 {
self.val
}
fn modulus() -> u32 {
M::umod()
}
fn mod_is_prime() -> bool {
false
}
}
pub struct ButterflyCache<T> {
pub sum_e: Vec<StaticModInt<T>>,
pub sum_ie: Vec<StaticModInt<T>>,
}
}
pub mod nums {
use std::mem::swap;
pub fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
let a = a.rem_euclid(b);
if a == 0 {
return (b, 0);
}
let mut s = b;
let mut t = a;
let mut m0 = 0;
let mut m1 = 1;
while t != 0 {
let u = s / t;
s -= t * u;
m0 -= m1 * u;
swap(&mut s, &mut t);
swap(&mut m0, &mut m1);
}
if m0 < 0 {
m0 += b / s;
}
(s, m0)
}
}
pub mod arraylist {
use std::ops::*;
use std::slice::Iter;
use std::fmt::Formatter;
use std::iter::FromIterator;
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct List<T> {
pub data: Vec<T>,
}
impl<T> List<T> {
#[inline]
pub fn new() -> List<T> {
List { data: vec![] }
}
#[inline]
pub fn init(init: T, n: isize) -> List<T>
where
T: Clone,
{
List {
data: vec![init; n as usize],
}
}
#[inline]
pub fn push(&mut self, item: T) {
self.data.push(item);
}
}
macro_rules! impl_idx {
($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => {
$(impl<$t> Index<$tpe> for List<$t> {
type Output = $($output)+;
#[inline]
fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
})*
$(impl<$t> Index<$tpe> for lst<$t> {
type Output = $($output)+;
#[inline]
fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
})*
}
}
macro_rules! impl_idx_mut {
($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => {
$(impl<T> IndexMut<$tpe> for List<T> {
#[inline]
fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
})*
$(impl<T> IndexMut<$tpe> for lst<T> {
#[inline]
fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
})*
};
}
macro_rules! impl_idx_slice {
($($tpe:ty),*) => {
impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*);
impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*);
};
}
impl_idx! {
isize, T [T], self, i, self.at(i),
char, T [T], self, i, self.at(i as isize - 'a' as isize)
}
impl_idx_slice! {
Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize>
}
impl_idx_mut! {
isize, self, i, self.at_mut(i),
char, self, i, self.at_mut(i as isize - 'a' as isize)
}
impl<T> FromIterator<T> for List<T> {
#[inline]
fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
List {
data: iter.into_iter().collect(),
}
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = std::vec::IntoIter<T>;
#[inline]
fn into_iter(self) -> std::vec::IntoIter<T> {
self.data.into_iter()
}
}
macro_rules! impl_traits {
($($tpe:tt),*) => {
$(
impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" "))
}
}
impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
self.data.fmt(f)
}
}
impl<'a, T> IntoIterator for &'a $tpe<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
#[inline]
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
)*
};
}
impl_traits!(List, lst);
impl<T> From<Vec<T>> for List<T> {
#[inline]
fn from(vec: Vec<T>) -> Self {
List { data: vec }
}
}
impl<T: Clone> From<&[T]> for List<T> {
#[inline]
fn from(slice: &[T]) -> Self {
slice.iter().cloned().collect()
}
}
impl<T> Deref for List<T> {
type Target = lst<T>;
#[inline]
fn deref(&self) -> &lst<T> {
lst::new(&self.data)
}
}
impl<T> DerefMut for List<T> {
#[inline]
fn deref_mut(&mut self) -> &mut lst<T> {
lst::new_mut(&mut self.data)
}
}
#[macro_export]
macro_rules! list {
() => { $crate::arraylist::List::new() };
($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) };
($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)};
($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) };
}
#[allow(non_camel_case_types)]
#[derive(PartialEq, Eq, PartialOrd, Ord)]
#[repr(transparent)]
pub struct lst<T> {
data: [T],
}
impl<T> lst<T> {
#[inline]
pub fn new(slice: &[T]) -> &Self {
unsafe { &*(slice as *const [T] as *const Self) }
}
#[inline]
pub fn new_mut(slice: &mut [T]) -> &mut Self {
unsafe { &mut *(slice as *mut [T] as *mut Self) }
}
#[inline]
fn at(&self, index: isize) -> &T {
if cfg!(debug_assertions) {
self.data.index(index as usize)
} else {
unsafe { self.data.get_unchecked(index as usize) }
}
}
#[inline]
fn at_mut(&mut self, index: isize) -> &mut T {
if cfg!(debug_assertions) {
self.data.index_mut(index as usize)
} else {
unsafe { self.data.get_unchecked_mut(index as usize) }
}
}
#[inline]
pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> {
if cfg!(debug_assertions) {
lst::new(self.data.index(self.rgm(range)))
} else {
unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) }
}
}
#[inline]
pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> {
if cfg!(debug_assertions) {
lst::new_mut(self.data.index_mut(self.rgm(range)))
} else {
let r = self.rgm(range);
unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) }
}
}
#[inline]
fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> {
(match r.start_bound() {
Bound::Included(x) => *x as usize,
Bound::Excluded(x) => *x as usize + 1,
_ => 0,
})
.max(0)..(match r.end_bound() {
Bound::Included(x) => *x as usize + 1,
Bound::Excluded(x) => *x as usize,
_ => self.data.len(),
})
.min(self.data.len())
}
}
impl lst<isize> {}
impl<T> Deref for lst<T> {
type Target = [T];
#[inline]
fn deref(&self) -> &[T] {
&self.data
}
}
impl<T> DerefMut for lst<T> {
#[inline]
fn deref_mut(&mut self) -> &mut [T] {
&mut self.data
}
}
impl<'a, T> From<&'a [T]> for &'a lst<T> {
#[inline]
fn from(slice: &'a [T]) -> Self {
lst::new(slice)
}
}
}
pub mod independent {
pub mod integer {
use std::fmt::Debug;
use std::fmt::Display;
use std::ops::*;
pub trait Num:
Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ PartialEq
+ PartialOrd
+ Copy
+ Debug
+ Display
{
fn to_u32(&self) -> u32;
fn to_u64(&self) -> u64;
fn to_u128(&self) -> u128;
fn to_i32(&self) -> i32;
fn to_i64(&self) -> i64;
fn to_i128(&self) -> i128;
fn to_usize(&self) -> usize;
fn to_isize(&self) -> isize;
fn to_f64(&self) -> f64;
fn from_i32(x: i32) -> Self;
fn from_u32(x: u32) -> Self;
fn from_u64(x: u64) -> Self;
fn from_u128(x: u128) -> Self;
fn from_i64(x: i64) -> Self;
fn from_i128(x: i128) -> Self;
fn from_usize(x: usize) -> Self;
fn from_isize(x: isize) -> Self;
fn from_f64(x: f64) -> Self;
fn zero() -> Self;
fn one() -> Self;
fn approx_sign(self) -> i32;
fn approx_eq(self, other: Self) -> bool {
(self - other).approx_sign() == 0
}
}
pub trait Int: Num + Rem<Output = Self> + RemAssign + Ord {
fn powint(&self, n: i64) -> Self;
fn cmul(&self, b: Self) -> Option<Self>;
}
pub trait Float: Num {}
#[macro_export]
macro_rules! impl_num_functions {
($to_op:expr, $from_op:expr, $appx_op:expr) => {
impl_num_functions!(
$to_op, $from_op,
to_u32, from_u32, u32,
to_u64, from_u64, u64,
to_u128, from_u128, u128,
to_i32, from_i32, i32,
to_i64, from_i64, i64,
to_i128, from_i128, i128,
to_usize, from_usize, usize,
to_isize, from_isize, isize,
to_f64, from_f64, f64
);
fn approx_sign(self) -> i32 {($appx_op)(self)}
};
($to_op:expr, $from_op:expr, $($tofn:ident, $fromfn:ident, $tpe:ident),*) => {
$(
fn $tofn(&self) -> $tpe {
$to_op(self) as $tpe
}
fn $fromfn(x: $tpe) -> Self {
$from_op(x)
}
)*
fn zero() -> Self {$from_op(0)}
fn one() -> Self {$from_op(1)}
};
}
macro_rules! impl_num_int {
($($tpe:ident),*) => {
$(
impl Num for $tpe {
impl_num_functions!(
|s: &Self| *s, |x| x as $tpe, |s: Self| if s < Self::zero() {-1} else if s > Self::zero() {1} else {0}
);
}
impl Int for $tpe {
fn powint(&self, n: i64) -> Self {
self.pow(n as u32) as $tpe
}
fn cmul(&self, b: Self) -> Option<Self> {self.checked_mul(b)}
}
)*
};
}
impl_num_int!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
pub const EPS: f64 = 1e-6;
impl Num for f64 {
impl_num_functions!(|s: &Self| *s, |x| x as f64, |s: Self| if s < -EPS {
-1
} else if s > EPS {
1
} else {
0
});
}
impl Float for f64 {}
}
}
pub mod macros {
pub mod assign_tmp {
#[macro_export]
macro_rules! tmp {
(($left:expr) $op:tt $right:expr) => {
let tmp = $right;
$left $op tmp;
}
}
}
}
pub mod scanner {
use std::io::{stdin, BufReader, Bytes, Read, Stdin};
use crate::types::*;
use std::str::FromStr;
pub struct Scanner {
buf: Bytes<BufReader<Stdin>>,
}
impl Scanner {
pub fn new() -> Scanner {
Scanner {
buf: BufReader::new(stdin()).bytes(),
}
}
#[inline]
fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
self.buf
.by_ref()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect()
}
#[inline]
pub fn read<T: FromStr>(&mut self) -> T {
self.string().parse().ok().unwrap()
}
#[inline]
pub fn string(&mut self) -> String {
self.token()
}
#[inline]
pub fn int(&mut self) -> idx {
self.read()
}
}
}
pub mod types {
pub use crate::arraylist::List as Seq;
#[allow(non_camel_case_types)]
pub type idx = isize;
pub use crate::list as seq;
pub use std::collections::hash_map as map;
pub use std::collections::HashMap as Map;
}