結果
| 問題 | No.1706 Many Bus Stops (hard) |
| ユーザー |
 BenkyouFpga
|
| 提出日時 | 2021-10-10 03:38:36 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,415 bytes |
| コンパイル時間 | 15,636 ms |
| コンパイル使用メモリ | 388,780 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-13 18:54:10 |
| 合計ジャッジ時間 | 17,182 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| 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 | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
コンパイルメッセージ
warning: unused import: `std::cmp`
--> src/main.rs:2:5
|
2 | use std::cmp;
| ^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `std::cmp::min`
--> src/main.rs:3:5
|
3 | use std::cmp::min;
| ^^^^^^^^^^^^^
warning: unused import: `std::collections::BTreeMap`
--> src/main.rs:4:5
|
4 | use std::collections::BTreeMap;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::process`
--> src/main.rs:5:5
|
5 | use std::process;
| ^^^^^^^^^^^^
warning: unused import: `std::collections::HashSet`
--> src/main.rs:8:5
|
8 | use std::collections::HashSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::collections::BTreeSet`
--> src/main.rs:10:5
|
10 | use std::collections::BTreeSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::collections::BinaryHeap`
--> src/main.rs:12:5
|
12 | use std::collections::BinaryHeap;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused imports: `Hash`, `Hasher`
--> src/main.rs:13:17
|
13 | use std::hash::{Hash, Hasher};
| ^^^^ ^^^^^^
warning: unnecessary parentheses around `while` condition
--> src/main.rs:143:10
|
143 | while(b>0){
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
143 - while(b>0){
143 + while b>0 {
|
warning: unnecessary parentheses around `while` condition
--> src/main.rs:159:14
|
159 | while(n != 0){
| ^ ^
|
help: remove these parentheses
|
159 - while(n != 0){
159 + while n != 0 {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:160:16
|
160 | if (n&1 == 1){ans = ans*x%MODu;}
| ^ ^
|
help: remove these parentheses
|
160 - if (n&1 == 1){ans = ans*x%MODu;}
160 + if n&1 == 1 {ans = ans*x%MODu;}
|
warning: unnecessary p
ソースコード
use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
.collect::<Vec<_>>();
std::str::from_utf8(&buf).unwrap()
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
pub trait BinarySearch<T> {
fn lower_bound(&self, x:&T) -> usize;
fn upper_bound(&self, x:&T) -> usize;
}
impl<T: Ord> BinarySearch<T> for VecDeque<T>{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
impl<T: Ord> BinarySearch<T> for [T]{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
fn comb(a:usize, b:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
let mut a = a;
let mut b = b;
if a == 0 && b == 0{return 1;}
if a<b || a<0{return 0;}
let mut tmp = ifac[a-b]*ifac[b]%MODu;
return tmp * fac[a]%MODu;
}
fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
if n == 0 && r == 0{
return 1;
}
return comb(n+r-1, r, fac, ifac);
}
fn modinv(a:usize, M:usize)->usize{
let mut b = M as i64;
let mut u = 1 as i64;
let mut v = 0 as i64;
let mut a = a as i64;
let mut m = M as i64;
while(b>0){
let mut t = a/b;
a -= t*b;
mem::swap(&mut a, &mut b);
u-=t*v;
mem::swap(&mut u, &mut v);
}
u%=m;
if u<0{u+=m;}
return u as usize;
}
fn modpow(x:usize, n:usize) -> usize{
let mut ans = 1;
let mut n = n as usize;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x%MODu;}
x = x*x%MODu;
n = n>>1;
}
ans
}
fn modpow2(x:i64, n:i64, m:i32) -> i64{
let mut ans = 1;
let mut n = n as i64;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x%m as i64;}
x = x*x%m as i64;
n = n>>1;
}
ans
}
fn invs(max:usize)->(Vec<usize>, Vec<usize>){
let mut fac = vec![0;max+1];
let mut ifac = vec![0;max+1];
fac[0] = 1;
ifac[0] = 1;
for i in 0..max{
fac[i+1] = fac[i] * (i+1)%MODu;
ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;
}
(fac, ifac)
}
#[derive(Copy, Clone, Eq, PartialEq)]
struct x{
a:i64,
b:i64,
c:i64,
d:i64,
}
impl Ord for x{
fn cmp(&self, other:&Self)->Ordering{
(other.b * (self.a)).cmp(&((self.b)*other.a))
}
}
impl PartialOrd for x {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn gcd(a:usize, b:usize)->usize{
if b==0{return a;}
return gcd(b, a%b);
}
fn prime_factor(n:usize)->HashMap<usize, usize>{
let mut res = HashMap::new();
let mut n = n;
for i in 2..n{
if i*i>n{break;}
while(n%i==0){
*res.entry(i).or_insert(0)+=1;
n/=i;
}
}
if n != 1{
res.insert(n, 1);
}
res
}
fn usize_multiply_is_overflow(a:usize, b:usize)->bool{
if a<std::usize::MAX/b{
return false;
}
else{
return true;
}
}
fn pow2(x:usize, n:usize) -> usize{
let mut ans = 1;
let mut n = n;
let mut x = x;
while(n != 0){
if (n&1 == 1){
if usize_multiply_is_overflow(ans, x){
return 0;
}
ans = ans*x;
}
n = n>>1;
if n == 0{
break;
}
if usize_multiply_is_overflow(x, x){
return 0;
}
x = x*x;
}
ans
}
fn tmp(x:usize, y:usize)->usize{
let mut ub = x+1;
let mut lb = 1;
while(ub-lb>1){
let mut mid = (ub+lb)/2;
let mut now = pow2(mid, y);
let mut ok = true;
if now == 0{
ok = false;
}
if now>x {
ok = false;
}
if ok{
lb = mid;
}
else{
ub = mid;
}
}
return lb;
}
struct segment_tree<I, Op>{
n: usize,
dat: Vec<I>,
op:Op,
e:I,
}
impl<I, Op> segment_tree<I, Op>
where Op: Fn(I, I) -> I, I:Copy{
pub fn new(n_:usize, op: Op, e:I)->Self{
let mut n = 1;
while(n<n_){n*=2;}
segment_tree{n: n, dat:vec![e; 2*n-1], op:op, e:e}
}
pub fn update(&mut self, k:usize, a:I){
let mut k = k;
k += self.n-1;
self.dat[k] = a;
while(k>0){
k = (k-1)/2;
self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]);
}
}
pub fn query_sub(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{
if r<=a || b<=l{return self.e;}
if a<=l && r<=b{return self.dat[k];}
else{
let mut vl = self.query_sub(a, b, k*2+1, l, (l+r)/2);
let mut vr = self.query_sub(a, b, k*2+2, (l+r)/2, r);
return (self.op)(vl, vr);
}
}
pub fn query(&self, a:usize, b:usize)->I{
return self.query_sub(a, b, 0, 0, self.n);
}
}
fn matmul_m(A:&Vec<Vec<i64>>, B:&Vec<Vec<i64>>) -> Vec<Vec<i64>>{
let mut C = vec![vec![0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
C[i][j] %= MOD;
}
}
}
return C;
}
fn matpow(A:&mut Vec<Vec<i64>>, n:usize) -> Vec<Vec<i64>>{
let mut B = vec![vec![0;A.len()];A.len()];
for i in 0..A.len(){
B[i][i] = 1;
}
let mut n = n;
let mut tmp = A.clone();
while(n>0){
if n&1 == 1{B = matmul_m(&B, &tmp);}
tmp = matmul_m(&tmp, &tmp);
n>>=1;
}
return B;
}
fn solve(){
let sssss = std::io::stdin();
let mut sc = Scanner { stdin: sssss.lock() };
let mut C:usize = sc.read();
let mut N:usize = sc.read();
let mut M:usize = sc.read();
let mut c= modinv(C, MODu) as i64;
let mut m = vec![vec![c, 0, 0, c],
vec![0, (C as i64-1)*c%MOD, (C as i64-1)*c%MOD, 0],
vec![1, 0, c, 0],
vec![0, 1, 0, c]];
let mut x = matpow(&mut m, N);
let mut res = modpow((1+MOD-x[0][0]) as usize %MODu, M);
println!("{}", (1+MOD-res as i64)%MOD);
}
fn main(){
solve();
}
const PI:f64 = std::f64::consts::PI;
pub static MOD:i64 = 1000000007;
pub static MODu:usize = 1000000007;
pub static MODi32:i32 = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 60;
const INFu:usize = 1<<62;
const INFu128:u128 = 1<<126;