結果
| 問題 | 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/0ba42c7ca36cd29d0ac8macro_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) -> StringwhereT: 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);}