結果
| 問題 |
No.737 PopCount
|
| ユーザー |
 sntea
|
| 提出日時 | 2018-09-29 14:26:11 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 1,000 ms |
| コード長 | 7,845 bytes |
| コンパイル時間 | 12,977 ms |
| コンパイル使用メモリ | 378,804 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-12 08:15:15 |
| 合計ジャッジ時間 | 13,572 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
コンパイルメッセージ
warning: unused macro definition: `printf`
--> src/main.rs:214:18
|
214 | macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
| ^^^^^^
|
= note: `#[warn(unused_macros)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:8:13
|
8 | let mut s = {
| ----^
| |
| help: remove this `mut`
...
217 | / input! {
218 | | n: usize,
219 | | }
| |_____- in this macro invocation
|
= note: `#[warn(unused_mut)]` on by default
= note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: method `pow` is never used
--> src/main.rs:89:16
|
83 | impl $name {
| ---------- method in this implementation
...
89 | fn pow(&self, x: i64) -> $name {
| ^^^
...
204 | make_modint!(1_000_000_000 + 7, ModInt);
| --------------------------------------- in this macro invocation
|
= note: `#[warn(dead_code)]` on by default
= note: this warning originates in the macro `make_modint` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
// from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
#[allow(unused_macros)]
macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } }
// macro_rules! debug { ($x: expr) => () }
#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
T: Iterator,
T::Item: std::fmt::Display
{
let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
res.pop();
res
}
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};
#[allow(unused_imports)]
use std::mem::swap;
macro_rules! make_modint {
($MOD: expr, $name: ident) => {
#[derive(Ord, Hash, Eq, PartialOrd, PartialEq)]
struct $name {
val: i64,
}
impl $name {
fn new(x: i64) -> $name {
let x = x%$MOD;
$name{val: if x < 0 { x+$MOD } else { x }}
}
fn pow(&self, x: i64) -> $name {
let mut res = $name::new(1);
let mut tmp = x;
let mut p = *self;
while tmp != 0 {
if tmp&1 == 1 {
res *= p;
}
tmp = tmp>>1;
p = p*p;
}
res
}
fn inv(&self) -> $name {
assert!(self.val != 0);
let mut a = self.val;
let mut b = $MOD;
let mut u = 1;
let mut v = 0;
use std::mem::swap;
while b != 0 {
let t = a/b;
a -= t*b;
swap(&mut a, &mut b);
u -= t*v;
swap(&mut u, &mut v);
}
$name::new(u)
}
}
impl std::clone::Clone for $name {
fn clone(&self) -> $name {
$name{ val: self.val }
}
}
impl std::marker::Copy for $name { }
impl std::ops::Add for $name {
type Output = $name;
fn add(self, y: $name) -> $name {
let tmp = self.val+y.val;
$name{val: if tmp >= $MOD {tmp-$MOD} else {tmp}}
}
}
impl std::ops::Neg for $name {
type Output = $name;
fn neg(self) -> $name {
$name::new(self.val)
}
}
impl std::ops::Sub for $name {
type Output = $name;
fn sub(self, other: $name) -> $name{
let tmp = self.val-other.val;
$name{val: if tmp < 0 {tmp+$MOD} else {tmp}}
}
}
impl std::ops::Mul for $name {
type Output = $name;
fn mul(self, y: $name) -> $name {
$name{val: (self.val*y.val)%$MOD}
}
}
impl std::ops::Div for $name {
type Output = $name;
fn div(self, other: $name) -> $name {
self*other.inv()
}
}
impl std::fmt::Display for $name {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl std::ops::AddAssign for $name {
fn add_assign(&mut self, other: $name) {
*self = *self+other;
}
}
impl std::ops::SubAssign for $name {
fn sub_assign(&mut self, other: $name) {
*self = *self-other;
}
}
impl std::ops::MulAssign for $name {
fn mul_assign(&mut self, other: $name) {
*self = *self*other;
}
}
impl std::ops::DivAssign for $name {
fn div_assign(&mut self, other: $name) {
*self = *self*other.inv();
}
}
impl std::fmt::Debug for $name {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
}
}
make_modint!(1_000_000_000 + 7, ModInt);
fn mint(x: i64) -> ModInt {
ModInt::new(x)
}
fn main() {
use std::io::Write;
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }
input! {
n: usize,
}
let n = n+1;
// let b = 64;
let mut cnt = 0;
let mut nt =n;
while nt != 0 {
cnt += 1;
nt >>= 1;
}
let b = cnt;
let mut dpc = vec![[mint(0); 2]; b+1];
dpc[0][0] = mint(1);
let mut dpv = vec![[mint(0); 2]; b+1];
for i in (0..b).rev() {
// debug!(i);
let mut nexc = vec![[mint(0); 2]; b+1];
nexc[0] = dpc[0];
if ((n>>i)&1) == 1 {
nexc[0][0] = mint(0);
nexc[0][1] = mint(1);
for j in 0..b {
nexc[j+1][0] = dpc[j][0];
nexc[j+1][1] = dpc[j+1][0] + dpc[j][1] + dpc[j+1][1];
}
} else {
for j in 0..b {
nexc[j+1][0] = dpc[j+1][0];
nexc[j+1][1] = dpc[j][1] + dpc[j+1][1];
}
}
let nexc = nexc;
let mut nexv = vec![[mint(0); 2]; b+1];
if ((n>>i)&1) == 1 {
for j in 0..b {
nexv[j+1][0] =
dpc[j][0] + mint(2) * dpv[j][0];
nexv[j+1][1] =
mint(2) * dpv[j+1][0] +
dpc[j][1] + mint(2) * dpv[j][1] +
mint(2) * dpv[j+1][1];
}
} else {
for j in 0..b {
nexv[j+1][0] = mint(2) * dpv[j+1][0];
nexv[j+1][1] =
dpc[j][1] + mint(2) * dpv[j][1] +
mint(2) * dpv[j+1][1];
}
}
dpc = nexc;
dpv = nexv;
// dpc.iter().for_each(|e| debug!(e));
// debug!("");
// dpv.iter().for_each(|e| debug!(e));
}
let ans =
dpv.iter()
.enumerate()
.map(|(i, &[_, x])| mint(i as i64) * x)
.fold(mint(0), |x, y| x + y);
printfln!("{}", ans);
// let ans = dp0.iter().enumerate()
// .map(|(i, v)| mint(i as i64) * v[1])
// .fold(mint(0), |x, y| x + y);
// printfln!("{}", ans);
}