結果
| 問題 |
No.3182 recurrence relation’s intersection sum
|
| ユーザー |
 Moss_Local
|
| 提出日時 | 2025-06-13 22:21:17 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 340 ms / 2,000 ms |
| コード長 | 8,157 bytes |
| コンパイル時間 | 11,881 ms |
| コンパイル使用メモリ | 399,208 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-13 22:21:44 |
| 合計ジャッジ時間 | 17,369 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
コンパイルメッセージ
warning: variable does not need to be mutable
--> src/main.rs:109:9
|
109 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:115:9
|
115 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:120:9
|
120 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:125:9
|
125 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable `K` should have a snake case name
--> src/main.rs:150:17
|
150 | let K = self.n();
| ^ help: convert the identifier to snake case (notice the capitalization): `k`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variable `M` should have a snake case name
--> src/main.rs:151:17
|
151 | let M = self.m();
| ^ help: convert the identifier to snake case: `m`
warning: variable `N` should have a snake case name
--> src/main.rs:152:17
|
152 | let N = other.n();
| ^ help: convert the identifier to snake case: `n`
warning: variable `K` should have a snake case name
--> src/main.rs:214:17
|
214 | let K = self.n();
| ^ help: convert the identifier to snake case (notice the capitalization): `k`
warning: variable `M` should have a snake case name
--> src/main.rs:215:17
|
215 | let M = self.m();
| ^ help: convert the identifier to snake case: `m`
warning: variable `N` should have a snake case name
--> src
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::*;
use std::collections::*;
use std::fmt::*;
use std::hash::*;
use std::io::BufRead;
use std::iter::FromIterator;
use std::*;
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
macro_rules! p {
($x:expr) => {
//if expr
println!("{}", $x);
};
}
macro_rules! vp {
// vector print separate with space
($x:expr) => {
println!(
"{}",
$x.iter()
.map(|x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
);
};
}
macro_rules! d {
($x:expr) => {
eprintln!("{:?}", $x);
};
}
macro_rules! yn {
($val:expr) => {
if $val {
println!("Yes");
} else {
println!("No");
}
};
}
macro_rules! map{
// declear btreemap
($($key:expr => $val:expr),*) => {
{
let mut map = ::std::collections::BTreeMap::new();
$(
map.insert($key, $val);
)*
map
}
};
}
macro_rules! set{
// declear btreemap
($($key:expr),*) => {
{
let mut set = ::std::collections::BTreeSet::new();
$(
set.insert($key);
)*
set
}
};
}
//input output
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut vec: Vec<i64> = read_vec();
(vec[0], vec[1])
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut vec: Vec<i64> = read_vec();
(vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut vec: Vec<usize> = read_vec();
(vec[0], vec[1])
}
fn readuuu() -> (usize, usize, usize) {
let mut vec: Vec<usize> = read_vec();
(vec[0], vec[1], vec[2])
}
pub mod matrix {
#[derive(Clone)]
pub struct Matrix {
pub v: Vec<Vec<i64>>,
}
impl Matrix {
pub fn identity(n: usize) -> Self {
let mut v = vec![vec![0; n]; n];
for i in 0..n {
v[i][i] = 1;
}
Matrix { v: v }
}
pub fn m(&self) -> usize {
self.v.len()
}
pub fn n(&self) -> usize {
self.v[0].len()
}
pub fn mul_rem(&self, other: &Self, mo: i64) -> Self {
assert!(self.n() == other.m());
let K = self.n();
let M = self.m();
let N = other.n();
let mut r = vec![vec![0; N]; M];
for i in 0..M {
for j in 0..N {
let mut v = 0;
for k in 0..K {
v += self.v[i][k] * other.v[k][j] % mo;
v %= mo;
}
r[i][j] = v;
}
}
Matrix { v: r }
}
pub fn pow(&self, k: u64, mo: i64) -> Self {
assert!(self.m() == self.n());
let mut k = k;
let mut x = Self::identity(self.m());
let mut y = self.clone();
while k > 0 {
if k & 1 > 0 {
x = y.mul_rem(&x, mo);
x %= mo;
}
y = y.mul_rem(&y, mo);
y %= mo;
k >>= 1;
}
x
}
}
use std::ops::*;
impl Add for Matrix {
type Output = Self;
fn add(self, other: Self) -> Self {
let mut r = self.v.clone();
for i in 0..self.m() {
for j in 0..self.n() {
r[i][j] += other.v[i][j];
}
}
Matrix { v: r }
}
}
impl Sub for Matrix {
type Output = Self;
fn sub(self, other: Self) -> Self {
let mut r = self.v.clone();
for i in 0..self.m() {
for j in 0..self.n() {
r[i][j] -= other.v[i][j];
}
}
Matrix { v: r }
}
}
impl Mul for Matrix {
type Output = Self;
fn mul(self, other: Self) -> Self {
assert!(self.n() == other.m());
let K = self.n();
let M = self.m();
let N = other.n();
let mut r = vec![vec![0; N]; M];
for i in 0..M {
for j in 0..N {
let mut v = 0;
for k in 0..K {
v += self.v[i][k] * other.v[k][j]; // mod over flow?
}
r[i][j] = v;
}
}
Matrix { v: r }
}
}
impl Rem<i64> for Matrix {
type Output = Self;
fn rem(self, mo: i64) -> Self {
let mut r = self.v.clone();
for i in 0..self.m() {
for j in 0..self.n() {
r[i][j] %= mo;
}
}
Matrix { v: r }
}
}
impl RemAssign<i64> for Matrix {
fn rem_assign(&mut self, mo: i64) {
for i in 0..self.m() {
for j in 0..self.n() {
self.v[i][j] %= mo;
}
}
}
}
}
fn matrix_pow(a: &Vec<i64>, mat: &Vec<Vec<i64>>, mut k: u64, mo: i64) -> Vec<i64> {
let n = a.len();
let mut res = vec![vec![0i64; n]; n];
for i in 0..n {
res[i][i] = 1;
}
let mut m = mat.clone();
while k > 0 {
if k & 1 == 1 {
res = mat_mul(&res, &m, mo);
}
m = mat_mul(&m, &m, mo);
k >>= 1;
}
let mut va = vec![0i64; n];
for i in 0..n {
for j in 0..n {
va[i] = (va[i] + res[i][j] * a[j] % mo) % mo;
}
}
va
}
fn mat_mul(a: &Vec<Vec<i64>>, b: &Vec<Vec<i64>>, mo: i64) -> Vec<Vec<i64>> {
let n = a.len();
let mut c = vec![vec![0i64; n]; n];
for i in 0..n {
for k in 0..n {
let aik = a[i][k];
if aik == 0 {
continue;
}
for j in 0..n {
c[i][j] = (c[i][j] + aik * b[k][j] % mo) % mo;
}
}
}
c
}
fn main() {
let (k, l, r) = readuuu();
let d = k + 4;
let idx_exp = k + 1;
let idx_a = k + 2;
let idx_s = k + 3;
// 二項係数
let mut cmb = vec![vec![0i64; k + 1]; k + 1];
for i in 0..=k {
cmb[i][0] = 1;
for j in 1..=i {
if j == i {
cmb[i][j] = 1;
} else {
cmb[i][j] = (cmb[i - 1][j - 1] + cmb[i - 1][j]) % MOD;
}
}
}
// 変換行列 T の構築
let mut mat = vec![vec![0i64; d]; d];
for i in 0..=k {
for j in 0..=i {
mat[i][j] = cmb[i][j];
}
}
mat[idx_exp][idx_exp] = (k as i64) % MOD;
mat[idx_a][idx_a] = (k as i64) % MOD;
mat[idx_a][k] = 1; // n^K term
mat[idx_a][idx_exp] = 1;
mat[idx_s][idx_s] = 1;
mat[idx_s][idx_a] = 1;
let mut v0 = vec![0i64; d];
v0[0] = 1;
v0[idx_exp] = 1;
v0[idx_a] = 1;
let v_l = matrix_pow(&v0, &mat, (l) as u64, MOD);
let v_r1 = matrix_pow(&v0, &mat, (r + 1) as u64, MOD);
let s_r1 = v_r1[idx_s] % MOD;
let s_l = v_l[idx_s] % MOD;
let ans = (s_r1 - s_l).rem_euclid(MOD);
println!("{}", ans);
}