結果
| 問題 | No.1100 Boxes |
| コンテスト | |
| ユーザー |
 sakikuroe
|
| 提出日時 | 2026-08-11 06:04:37 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 11 ms / 2,000 ms |
| + 225µs | |
| コード長 | 19,070 bytes |
| 記録 | |
| コンパイル時間 | 919 ms |
| コンパイル使用メモリ | 193,208 KB |
| 実行使用メモリ | 5,888 KB |
| 最終ジャッジ日時 | 2026-08-11 06:04:41 |
| 合計ジャッジ時間 | 3,235 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 36 |
コンパイルメッセージ
warning: unused import: `super::modulo`
--> src/main.rs:184:17
|
184 | use super::modulo;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default
warning: unused imports: `arch::x86_64` and `sync`
--> src/main.rs:185:23
|
185 | use std::{arch::x86_64, sync};
| ^^^^^^^^^^^^ ^^^^
warning: unused imports: `ffi`, `fs`, `io`, and `ptr`
--> src/main.rs:456:23
|
456 | use std::{ffi, fs, io, ptr};
| ^^^ ^^ ^^ ^^^
warning: unused import: `std::os::unix`
--> src/main.rs:459:17
|
459 | use std::os::unix;
| ^^^^^^^^^^^^^
ソースコード
use anmitsu::modulo998244353::{combinatorics::Combinatorics, modint::ModInt998244353};
use proconio::input;
fn main() {
input! {
n: usize, k: usize,
}
// let mut f = FPS::new(vec![]);
// f += FPS::new(vec![0, 1]).exp(n).unwrap().pow(k, n);
// f -= (FPS::new(vec![0, 1]).exp(n).unwrap() - FPS::new(vec![2])).pow(k, n);
// f *= FPS::new(vec![2]).inverse(n).unwrap();
// let mut comb = Combinatorics::new();
// println!("{}", ModInt998244353::new(f.get(n) as u64) * comb.fact(n));
let mut ans = ModInt998244353::new(0);
let mut comb = Combinatorics::new();
let mut p = ModInt998244353::new(1);
let b = ModInt998244353::new(0) - 2;
for i in 1..=k {
ans += comb.comb(k as u64, i) * p * ModInt998244353::new((k - i) as u64).pow(n);
p *= b;
}
println!("{}", ans);
}
// The following is anmitsu (CC0-1.0), a Rust library for competitive
// programming, bundled into this file with unused items removed.
// https://github.com/sakikuroe/algorithms-and-data-structures-rs
mod anmitsu {
pub mod modulo998244353 {
pub mod combinatorics {
use super::modint;
use super::modulo;
const MAX_TABLE_N: usize = 1 << 25;
const BLOCK_SIZE: usize = 1 << 10;
#[derive(Debug, Clone)]
pub struct Combinatorics {
fact: Vec<modint::ModInt998244353>,
inv_fact: Vec<modint::ModInt998244353>,
inv: Vec<modint::ModInt998244353>,
}
impl Combinatorics {
pub fn new() -> Self {
// 初期値として `0! = 1` と `inv_fact(0) = 1` を持たせる。
let one = modint::ModInt998244353::new_raw(1);
Combinatorics {
fact: vec![one],
inv_fact: vec![one],
inv: vec![modint::ModInt998244353::default()],
}
}
fn ensure_table(&mut self, n: usize) {
if n >= modulo::M as usize {
return;
}
// メモリ使用量を制御するため、ある閾値より大きい場合はテーブルを拡張しない。
if n > MAX_TABLE_N {
return;
}
// `modulo::M` は素数なので、`i < modulo::M` の範囲の `i!` は 0 にならない。
// よって `inv_fact` を保持しても逆元が存在し続ける。
let max_len = (MAX_TABLE_N + 1).min(modulo::M as usize);
// `n` を含むブロックまでを一括で確保し、同一ブロック内の逐次呼び出しで
// 再拡張が発生しないようにする。
let mut target_len = (n / BLOCK_SIZE + 1) * BLOCK_SIZE;
target_len = target_len.min(max_len);
// すでに必要な範囲が構築済みなら何もしない。
if self.fact.len() >= target_len {
return;
}
// 既存の末尾から必要な範囲までだけを伸ばす。
let old_len = self.fact.len();
self.fact
.resize(target_len, modint::ModInt998244353::default());
for i in old_len..target_len {
self.fact[i] = self.fact[i - 1] * i as u32;
}
self.inv_fact
.resize(target_len, modint::ModInt998244353::default());
let last = target_len - 1;
// `inv_fact[last]` を 1 回だけ計算し、そこから逆向きに連鎖させる。
self.inv_fact[last] = self.fact[last].inv().unwrap();
// 新しく伸ばした区間だけ `inv_fact` を埋める。
for i in (old_len + 1..=last).rev() {
self.inv_fact[i - 1] = self.inv_fact[i] * i as u32;
}
self.inv
.resize(target_len, modint::ModInt998244353::default());
// `inv` は `fact` と `inv_fact` から計算できるため、伸長区間だけを更新する。
for i in old_len..target_len {
self.inv[i] = self.inv_fact[i] * self.fact[i - 1];
}
}
fn fact_without_extending(&self, n: usize) -> modint::ModInt998244353 {
if n == 0 {
return modint::ModInt998244353::new_raw(1);
}
// テーブルを拡張しない場合でも、既存の末尾から乗算を再開する。
let start = self.fact.len() - 1;
let mut res = self.fact[start];
for i in (start + 1)..=n {
res *= i as u32;
}
res
}
pub fn fact(&mut self, n: usize) -> modint::ModInt998244353 {
// `n >= M` のとき `n!` は `M` を因数に持つため、常に 0 になる。
if n >= modulo::M as usize {
return modint::ModInt998244353::new_raw(0);
}
if n <= MAX_TABLE_N {
// 参照頻度が高い範囲はテーブル化し、同一ブロック内での連続クエリーを高速化する。
self.ensure_table(n);
return self.fact[n];
}
// メモリ使用量を抑えるため、閾値より大きい場合はテーブル化しない。
self.fact_without_extending(n)
}
pub fn inv_fact(&mut self, n: usize) -> modint::ModInt998244353 {
// `n >= M` のとき `n! = 0` なので逆元は存在しない。
// この実装では 0 を返して呼び出し側に委ねる。
if n >= modulo::M as usize {
return modint::ModInt998244353::new_raw(0);
}
if n <= MAX_TABLE_N {
// `inv_fact` は `inv(m!)` の 1 回の計算から逆向きに埋められるため、
// 連続クエリーで `pow` が多発しないようにテーブルを伸ばす。
self.ensure_table(n);
return self.inv_fact[n];
}
// 閾値より大きい場合は、`fact(n)` を愚直に計算してから 1 回だけ `inv` を呼ぶ。
self.fact_without_extending(n).inv().unwrap()
}
pub fn comb(&mut self, n: u64, k: usize) -> modint::ModInt998244353 {
if k as u64 > n {
// 定義により `k > n` のとき `C(n, k) = 0`。
return modint::ModInt998244353::new_raw(0);
}
assert!(
k < modulo::M as usize,
"k must be less than MOD for comb without Lucas"
);
let n0 = (n % modulo::M as u64) as usize;
if n0 < k {
return modint::ModInt998244353::new_raw(0);
}
self.fact(n0) * self.inv_fact(k) * self.inv_fact(n0 - k)
}
}
}
pub mod convolution_mont {
#![cfg(target_arch = "x86_64")]
use super::modulo;
use std::{arch::x86_64, sync};
}
pub mod modint {
use std::{fmt, ops};
const MOD: u32 = 998244353; // 998244353 = 119 * 2^23 + 1 という NTT フレンドリーな素数である。
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct ModInt998244353 {
val: u32,
}
impl ModInt998244353 {
pub fn new(n: u64) -> Self {
// n を MOD で還元し、[0, MOD) の範囲に収める。
ModInt998244353 {
val: (n % MOD as u64) as u32,
}
}
pub fn new_raw(n: u32) -> Self {
// 呼び出し側が n < MOD を保証している前提で、還元処理を省略して直接構築する。
assert!(n < MOD, "Raw value {} must be less than MOD {}", n, MOD);
ModInt998244353 { val: n }
}
pub fn inv(&self) -> Option<Self> {
if self.val == 0 {
None
} else {
// フェルマーの小定理より、MOD が素数のとき a^(MOD-2) mod MOD が乗法逆元となる。
Some(self.pow((MOD - 2) as usize))
}
}
pub fn pow(&self, mut n: usize) -> Self {
// 累積する結果。初期値は乗法単位元の 1 である。
let mut res = ModInt998244353::new_raw(1);
// 2 乗を繰り返していく途中経過の底。
let mut base = *self;
// 二分累乗法 (繰り返し二乗法) により、O(log n) 回の乗算で self^n を計算する。
while n > 0 {
// n の最下位ビットが 1 の場合、現在の底を結果に掛け合わせる。
if n % 2 == 1 {
res *= base;
}
// 底を 2 乗し、次の桁に備える。
base *= base;
n /= 2;
}
res
}
}
impl From<u32> for ModInt998244353 {
fn from(num: u32) -> Self {
// u64 に拡張して new に委譲し、MOD による還元を行う。
ModInt998244353::new(num as u64)
}
}
impl From<i32> for ModInt998244353 {
fn from(num: i32) -> Self {
// num が負の場合、num % MOD as i32 は負の値になり得るため、MOD を加えて非負の値に補正する。
let val = if num >= 0 {
num as u64
} else {
(num % MOD as i32 + MOD as i32) as u64
};
ModInt998244353::new(val)
}
}
impl ops::Add for ModInt998244353 {
type Output = Self;
fn add(mut self, rhs: Self) -> Self::Output {
// += 演算子に処理を委譲し、結果を新しい値として返す。
self += rhs;
self
}
}
impl ops::Add<u32> for ModInt998244353 {
type Output = Self;
fn add(mut self, rhs: u32) -> Self::Output {
// += 演算子に処理を委譲し、結果を新しい値として返す。
self += rhs;
self
}
}
impl ops::AddAssign for ModInt998244353 {
fn add_assign(&mut self, rhs: Self) {
// self.val, rhs.val はいずれも MOD 未満なので、和は u32 でオーバーフローしない。
self.val += rhs.val;
// 和が MOD 以上になった場合のみ MOD を引き、[0, MOD) の範囲に戻す。
if self.val >= MOD {
self.val -= MOD;
}
}
}
impl ops::AddAssign<u32> for ModInt998244353 {
fn add_assign(&mut self, rhs: u32) {
// rhs は MOD 未満とは限らないため、先に MOD で還元しておく。
let rhs_mod = rhs % MOD;
self.val += rhs_mod;
// 和が MOD 以上になった場合のみ MOD を引き、[0, MOD) の範囲に戻す。
if self.val >= MOD {
self.val -= MOD;
}
}
}
impl ops::Sub for ModInt998244353 {
type Output = Self;
fn sub(mut self, rhs: Self) -> Self::Output {
// -= 演算子に処理を委譲し、結果を新しい値として返す。
self -= rhs;
self
}
}
impl ops::Sub<u32> for ModInt998244353 {
type Output = Self;
fn sub(mut self, rhs: u32) -> Self::Output {
// -= 演算子に処理を委譲し、結果を新しい値として返す。
self -= rhs;
self
}
}
impl ops::SubAssign for ModInt998244353 {
fn sub_assign(&mut self, rhs: Self) {
// self.val が rhs.val 以上であれば、そのまま引くだけで [0, MOD) の範囲に収まる。
if self.val >= rhs.val {
self.val -= rhs.val;
} else {
// self.val が rhs.val 未満の場合はアンダーフローするため、先に MOD を足してから引く。
self.val += MOD - rhs.val;
}
}
}
impl ops::SubAssign<u32> for ModInt998244353 {
fn sub_assign(&mut self, rhs: u32) {
// rhs は MOD 未満とは限らないため、先に MOD で還元しておく。
let rhs_mod = rhs % MOD;
// self.val が rhs_mod 以上であれば、そのまま引くだけで [0, MOD) の範囲に収まる。
if self.val >= rhs_mod {
self.val -= rhs_mod;
} else {
// self.val が rhs_mod 未満の場合はアンダーフローするため、先に MOD を足してから引く。
self.val += MOD - rhs_mod;
}
}
}
impl ops::Mul for ModInt998244353 {
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
// self.val * rhs.val は最大で (MOD - 1)^2 程度になり u32 を超えるため、
// u64 に拡張してから乗算し、new で MOD により還元する。
ModInt998244353::new((self.val as u64) * (rhs.val as u64))
}
}
impl ops::Mul<u32> for ModInt998244353 {
type Output = Self;
fn mul(self, rhs: u32) -> Self::Output {
// self.val * rhs は最大で (MOD - 1) * (u32::MAX) 程度になり u32 を超えるため、
// u64 に拡張してから乗算し、new で MOD により還元する。
ModInt998244353::new((self.val as u64) * (rhs as u64))
}
}
impl ops::MulAssign for ModInt998244353 {
fn mul_assign(&mut self, rhs: Self) {
// 乗算演算子に処理を委譲する。
*self = *self * rhs;
}
}
impl ops::MulAssign<u32> for ModInt998244353 {
fn mul_assign(&mut self, rhs: u32) {
// 乗算演算子に処理を委譲する。
*self = *self * rhs;
}
}
impl ops::Div for ModInt998244353 {
type Output = Self;
fn div(self, rhs: Self) -> Self::Output {
// 除算を乗算として扱うため、除数の逆元をあらかじめ計算する。
// 逆元が存在しない (rhs が 0 の) 場合はパニックする。
let inv_rhs = rhs.inv().unwrap_or_else(|| {
panic!("Division by zero is not allowed for ModInt998244353")
});
self * inv_rhs
}
}
impl ops::Div<u32> for ModInt998244353 {
type Output = Self;
fn div(self, rhs: u32) -> Self::Output {
// rhs を ModInt998244353 に変換したうえで、除算演算子に処理を委譲する。
let rhs_mod = ModInt998244353::new(rhs as u64);
let inv_rhs = rhs_mod.inv().unwrap_or_else(|| {
panic!("Division by zero is not allowed for ModInt998244353")
});
self * inv_rhs
}
}
impl ops::DivAssign for ModInt998244353 {
fn div_assign(&mut self, rhs: Self) {
// 除算演算子に処理を委譲する。
*self = *self / rhs;
}
}
impl ops::DivAssign<u32> for ModInt998244353 {
fn div_assign(&mut self, rhs: u32) {
// 除算演算子に処理を委譲する。
*self = *self / rhs;
}
}
impl ops::Neg for ModInt998244353 {
type Output = Self;
fn neg(self) -> Self::Output {
// 0 の加法逆元は 0 自身であり、それ以外は MOD から val を引いた値が加法逆元となる。
if self.val == 0 {
Self::new_raw(0)
} else {
Self::new_raw(MOD - self.val)
}
}
}
impl fmt::Display for ModInt998244353 {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.val)
}
}
impl Default for ModInt998244353 {
fn default() -> Self {
ModInt998244353 { val: 0 }
}
}
}
pub mod modulo {
pub const M: u32 = 998244353;
}
}
pub mod io {
pub mod fastio {
use std::{ffi, fs, io, ptr};
#[cfg(target_os = "linux")]
use std::os::unix;
#[cfg(target_os = "linux")]
#[link(name = "c")]
unsafe extern "C" {}
}
}
}