結果
| 問題 | No.1259 スイッチ |
| ユーザー |
 atcoder8
|
| 提出日時 | 2023-04-05 12:41:18 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 19 ms / 2,000 ms |
| コード長 | 18,720 bytes |
| コンパイル時間 | 12,647 ms |
| コンパイル使用メモリ | 403,308 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-01 23:21:23 |
| 合計ジャッジ時間 | 15,276 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 61 |
ソースコード
use atcoder8_library::modint::Modint1000000007;use crate::atcoder8_library::{factorial::Factorial, modint::Pow};type Mint = Modint1000000007;fn main() {println!("{}", solve().val());}fn solve() -> Mint {let (n, k, m) = {let mut line = String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)};let mut fac: Factorial<Mint> = Factorial::new();// k回の操作で1に戻る <=> 1を含む長さがkの約数のループが存在する// n以下のkの約数dに対して// * 1を含むループを構成する1以外のd-1個の要素を2,3,...,nから選んで並べる: P(n-1,d-1)// * 残りのn-d個の要素についてそれぞれ遷移先を1,2,...,nから任意に選ぶ: n^(n-d)// 条件を満たす組み合わせの総数: \sum_{d|k} P(n-1,d-1)n^(n-d)let back_to_one_comb_num = (1..=n).filter(|&d| k % d == 0).fold(Mint::new(0), |acc, d| {acc + fac.permutations(n - 1, d - 1) * Mint::new(n).pow(n - d)});if m == 1 {// k回の操作で1に戻る組み合わせの数back_to_one_comb_num} else {// 1に戻らない場合の遷移先はn-1通り存在するため，// mになるような組み合わせの数は1に戻らない組み合わせの数をn-1で割った値になる(Mint::new(n).pow(n) - back_to_one_comb_num) / (n - 1)}}pub mod atcoder8_library {pub mod modint {use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, ShrAssign, Sub, SubAssign,};pub trait RemEuclidU32 {fn rem_euclid_u32(self, modulus: u32) -> u32;}/// Calculate the modular multiplicative inverse of `a` with `m` as modulus.pub fn modinv(a: u32, m: u32) -> u32 {assert!(m >= 2);let (mut a, mut b, mut s, mut t) = (a as i64, m as i64, 1, 0);while b != 0 {let q = a / b;a -= q * b;std::mem::swap(&mut a, &mut b);s -= q * t;std::mem::swap(&mut s, &mut t);}assert_eq!(a.abs(),1,"The inverse does not exist. gcd(a, m) = {}",a.abs());s %= m as i64;if s < 0 {s += m as i64;}s as u32}/// This macro implements rem_euclid_u32 for signed integer types of 32 bits or less.macro_rules! impl_rem_euclid_u32_for_small_signed {($($small_signed_type:tt),*) => {$(impl RemEuclidU32 for $small_signed_type {fn rem_euclid_u32(self, modulus: u32) -> u32 {let ret = (self as i32) % (modulus as i32);if ret >= 0 {ret as u32} else {(ret + modulus as i32) as u32}}})*};}/// This macro implements rem_euclid_u32 for 64-bit signed integer types (including isize).macro_rules! impl_rem_euclid_u32_for_large_signed {($($large_signed_type:tt),*) => {$(impl RemEuclidU32 for $large_signed_type {fn rem_euclid_u32(self, modulus: u32) -> u32 {let ret = (self as i64) % (modulus as i64);if ret >= 0 {ret as u32} else {(ret + modulus as i64) as u32}}})*};}/// This macro implements rem_euclid_u32 for unsigned integer types greater than 32 bits.macro_rules! impl_rem_euclid_u32_for_small_unsigned {($($small_unsigned_type:tt),*) => {$(impl RemEuclidU32 for $small_unsigned_type {fn rem_euclid_u32(self, modulus: u32) -> u32 {self as u32 % modulus}})*};}/// This macro implements rem_euclid_u32 for 64-bit and larger unsigned integer types (including usize).macro_rules! impl_rem_euclid_u32_for_large_unsigned {($($large_unsigned_type:tt),*) => {$(impl RemEuclidU32 for $large_unsigned_type {fn rem_euclid_u32(self, modulus: u32) -> u32 {(self % modulus as $large_unsigned_type) as u32}})*};}// Implement rem_euclid_u32 for signed integer types of 32 bits or less.impl_rem_euclid_u32_for_small_signed!(i8, i16, i32);// Implement rem_euclid_u32 for 64-bit signed integer types (including isize).impl_rem_euclid_u32_for_large_signed!(i64, isize);// Implement rem_euclid_u32 for unsigned integer types of 32 bits or more.impl_rem_euclid_u32_for_small_unsigned!(u8, u16, u32);// Implement rem_euclid_u32 for unsigned integer types (including usize) of 64 bits or more.impl_rem_euclid_u32_for_large_unsigned!(u64, u128, usize);// Implement rem_euclid_u32 for i128.impl RemEuclidU32 for i128 {fn rem_euclid_u32(self, modulus: u32) -> u32 {let ret = self % (modulus as i128);if ret >= 0 {ret as u32} else {(ret + modulus as i128) as u32}}}pub trait Pow<T: Copy + ShrAssign> {fn pow(self, n: T) -> Self;}/// Macro to overload binary operation with `$modint_type` for each integer typemacro_rules! impl_ops {($modint_type:tt, $($other_type:tt),*) => {$(impl Add<$other_type> for $modint_type {type Output = Self;fn add(self, rhs: $other_type) -> Self::Output {self + Self::new(rhs)}}impl Add<$modint_type> for $other_type {type Output = $modint_type;fn add(self, rhs: $modint_type) -> Self::Output {$modint_type::new(self) + rhs}}impl Sub<$other_type> for $modint_type {type Output = Self;fn sub(self, rhs: $other_type) -> Self::Output {self - Self::new(rhs)}}impl Sub<$modint_type> for $other_type {type Output = $modint_type;fn sub(self, rhs: $modint_type) -> Self::Output {$modint_type::new(self) - rhs}}impl Mul<$other_type> for $modint_type {type Output = Self;fn mul(self, rhs: $other_type) -> Self::Output {self * Self::new(rhs)}}impl Mul<$modint_type> for $other_type {type Output = $modint_type;fn mul(self, rhs: $modint_type) -> Self::Output {$modint_type::new(self) * rhs}}impl Div<$other_type> for $modint_type {type Output = Self;fn div(self, rhs: $other_type) -> Self::Output {self / Self::new(rhs)}}impl Div<$modint_type> for $other_type {type Output = $modint_type;fn div(self, rhs: $modint_type) -> Self::Output {$modint_type::new(self) / rhs}}impl AddAssign<$other_type> for $modint_type {fn add_assign(&mut self, other: $other_type) {*self = *self + Self::new(other);}}impl SubAssign<$other_type> for $modint_type {fn sub_assign(&mut self, other: $other_type) {*self = *self - Self::new(other);}}impl MulAssign<$other_type> for $modint_type {fn mul_assign(&mut self, other: $other_type) {*self = *self * Self::new(other);}}impl DivAssign<$other_type> for $modint_type {fn div_assign(&mut self, other: $other_type) {*self = *self / Self::new(other);}})*};}/// This macro defines powers of Modint for unsigned integer types.macro_rules! impl_power_for_unsigned {($modint_type:tt, $($unsigned_type:tt),*) => {$(impl Pow<$unsigned_type> for $modint_type {fn pow(self, mut n: $unsigned_type) -> Self {let mut ret = Self::new(1);let mut mul = self;while n != 0 {if n & 1 == 1 {ret *= mul;}mul *= mul;n >>= 1;}ret}})*};}/// This macro defines powers of Modint for signed integer types of 32 bits or less.macro_rules! impl_power_for_small_signed {($modint_type:tt, $($small_signed_type:tt),*) => {$(impl Pow<$small_signed_type> for $modint_type {fn pow(self, n: $small_signed_type) -> Self {if n >= 0 {self.pow(n as u32)} else {self.pow(-n as u32).inv()}}})*};}/// This macro defines the power of Modint for 64-bit signed integer types (including isize).macro_rules! impl_power_for_large_signed {($modint_type:tt, $($large_signed_type:tt),*) => {$(impl Pow<$large_signed_type> for $modint_type {fn pow(self, n: $large_signed_type) -> Self {if n >= 0 {self.pow(n as u64)} else {self.pow(-n as u64).inv()}}})*};}/// This macro generates Modint by specifying the type name and modulus.macro_rules! generate_modint {($modint_type:tt, $modulus:literal) => {#[derive(Debug, Default, Hash, Clone, Copy, PartialEq, Eq)]pub struct $modint_type {val: u32,}impl $modint_type {const MOD: u32 = $modulus;}impl $modint_type {pub fn new<T: RemEuclidU32>(val: T) -> Self {Self {val: val.rem_euclid_u32($modulus),}}pub fn frac<T: RemEuclidU32>(numer: T, denom: T) -> Self {Self::new(numer) / Self::new(denom)}pub fn raw(val: u32) -> Self {Self { val }}pub fn val(&self) -> u32 {self.val}pub fn inv(&self) -> Self {Self::new(modinv(self.val, $modulus))}}impl<T: RemEuclidU32> From<T> for $modint_type {fn from(val: T) -> Self {Self::new(val)}}impl Add for $modint_type {type Output = Self;fn add(self, rhs: Self) -> Self::Output {Self::new(self.val + rhs.val)}}impl Sub for $modint_type {type Output = Self;fn sub(self, rhs: Self) -> Self::Output {Self::new(self.val + $modulus - rhs.val)}}impl Mul for $modint_type {type Output = Self;fn mul(self, rhs: Self) -> Self::Output {Self::new(self.val as u64 * rhs.val as u64)}}impl Div for $modint_type {type Output = Self;#[allow(clippy::suspicious_arithmetic_impl)]fn div(self, rhs: Self) -> Self::Output {self * rhs.inv()}}impl AddAssign for $modint_type {fn add_assign(&mut self, other: Self) {*self = *self + other;}}impl SubAssign for $modint_type {fn sub_assign(&mut self, other: Self) {*self = *self - other;}}impl MulAssign for $modint_type {fn mul_assign(&mut self, other: Self) {*self = *self * other;}}impl DivAssign for $modint_type {fn div_assign(&mut self, other: Self) {*self = *self / other;}}impl Neg for $modint_type {type Output = Self;fn neg(self) -> Self::Output {Self::new(Self::MOD - self.val)}}// Define a binary operation between each integer type and $modint_type.impl_ops!($modint_type,i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);// Define powers of Modint for unsigned integer types.impl_power_for_unsigned!($modint_type, u8, u16, u32, u64, u128, usize);// Define powers of Modint for signed integer types of 32 bits or less.impl_power_for_small_signed!($modint_type, i8, i16, i32);// Define Modint powers for 64-bit signed integer types (including isize).impl_power_for_large_signed!($modint_type, i64, isize);// Define the power of Modint for 128-bit signed integer types.impl Pow<i128> for $modint_type {fn pow(self, n: i128) -> Self {if n >= 0 {self.pow(n as u128)} else {self.pow(-n as u128).inv()}}}};}// Define Modint with 998244353 as modulusgenerate_modint!(Modint998244353, 998244353);// Define Modint with 1000000007 as modulusgenerate_modint!(Modint1000000007, 1000000007);}pub mod factorial {use std::ops::{Div, Mul};pub struct Factorial<T> {fac: Vec<T>,}impl<T> Default for Factorial<T>whereT: Clone + From<usize> + Mul<Output = T> + Div<Output = T>,{fn default() -> Self {Self::new()}}impl<T> Factorial<T>whereT: Clone + From<usize> + Mul<Output = T> + Div<Output = T>,{/// Constructs a new, empty `Factorial<T>`.pub fn new() -> Self {Self {fac: vec![T::from(1)],}}/// Returns the factorial of `n`.pub fn factorial(&mut self, n: usize) -> T {if self.fac.len() < n + 1 {for i in (self.fac.len() - 1)..n {self.fac.push(self.fac[i].clone() * (i + 1).into());}}self.fac[n].clone()}/// Returns the number of choices when selecting `k` from `n` and arranging them in a row.pub fn permutations(&mut self, n: usize, k: usize) -> T {if n < k {T::from(0)} else {self.factorial(n) / self.factorial(n - k)}}/// Returns the number of choices to select `k` from `n`.pub fn combinations(&mut self, n: usize, k: usize) -> T {if n < k {T::from(0)} else {self.factorial(n) / (self.factorial(k) * self.factorial(n - k))}}/// Calculate the number of cases when sample of `k` elements from a set of `n` elements, allowing for duplicates.pub fn combinations_with_repetition(&mut self, n: usize, k: usize) -> T {if n == 0 {if k == 0 {T::from(1)} else {T::from(0)}} else {self.combinations(n + k - 1, k)}}}}}