結果
| 問題 | No.3662 yuu Hates Sigma Problem |
| コンテスト | |
| ユーザー |
 urectanc
|
| 提出日時 | 2026-08-31 23:45:32 |
| 言語 | Rust (1.97.1 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 21 ms / 2,000 ms |
| + 824µs | |
| コード長 | 9,259 bytes |
| 記録 | |
| コンパイル時間 | 3,439 ms |
| コンパイル使用メモリ | 198,016 KB |
| 実行使用メモリ | 7,728 KB |
| 最終ジャッジ日時 | 2026-08-31 23:45:50 |
| 合計ジャッジ時間 | 6,822 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| subtask1. | 20 % | AC * 19 |
| subtask2. | 30 % | AC * 13 |
| subtask3. | 50 % | AC * 49 |
| 合計 | 2.5 * 100% = 250 点 |
ソースコード
use proconio::input;
use urectanc::modint::ModInt998244353;
type Mint = ModInt998244353;
fn main() {
input! {
n: usize,
a: [usize; n],
}
let mut ans = Mint::zero();
for k in 0..20 {
let mut count = [0; 2];
for i in 0..n {
count[i >> k & 1] += 1;
}
for (i, &a) in a.iter().enumerate() {
ans += a * (count[(i >> k & 1) ^ 1] << k);
}
}
println!("{ans}");
}
pub mod urectanc {
pub mod modint {
use std::{
fmt::Debug,
ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign},
};
pub trait Modulus: 'static + Clone + Copy + Debug + Default + PartialEq + Eq {
const MOD: u32;
}
macro_rules! define_modulus {
($name:ident, $modulus:expr) => {
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct $name;
impl Modulus for $name {
const MOD: u32 = const {
assert!($modulus < (1u32 << 31));
$modulus
};
}
};
}
define_modulus!(Mod998244353, 998244353);
define_modulus!(Mod1000000007, 1000000007);
pub type ModInt998244353 = ModInt<Mod998244353>;
pub type ModInt1000000007 = ModInt<Mod1000000007>;
#[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
#[repr(transparent)]
pub struct ModInt<M> {
val: u32,
_phantom: std::marker::PhantomData<fn() -> M>,
}
impl<M: Modulus> ModInt<M> {
pub fn modulus() -> u32 {
M::MOD
}
pub fn new(val: u32) -> Self {
Self::from(val)
}
pub fn new_unchecked(val: u32) -> Self {
Self {
val,
_phantom: std::marker::PhantomData,
}
}
#[deprecated]
pub fn raw(val: u32) -> Self {
Self::new_unchecked(val)
}
pub fn zero() -> Self {
Self::new_unchecked(0)
}
pub fn one() -> Self {
Self::new_unchecked(1)
}
pub fn val(&self) -> u32 {
self.val
}
pub fn pow(&self, mut exp: usize) -> Self {
let mut res = Self::one();
let mut pow = *self;
while exp > 0 {
if exp & 1 == 1 {
res *= pow;
}
pow *= pow;
exp >>= 1;
}
res
}
pub fn inv(&self) -> Self {
self.checked_inv().unwrap_or_else(|| {
panic!(
"inverse not exist for {} (mod {})",
self.val(),
Self::modulus()
)
})
}
pub fn checked_inv(&self) -> Option<Self> {
let x = self.val() as i32;
let m = Self::modulus() as i32;
let mut u = (m, 0);
let mut v = (x, 1);
while v.0 != 0 {
let q = u.0 / v.0;
(u, v) = (v, (u.0 % v.0, u.1 - q * v.1));
}
(u.0 == 1).then_some(Self::new_unchecked(
if u.1 < 0 { u.1 + m } else { u.1 } as u32
))
}
fn to_rational(self) -> (i64, i64) {
let m = Self::modulus() as i64;
let mut u = (m, 0);
let mut v = (self.val() as i64, 1);
while v.0 * v.0 * 2 > m {
let q = u.0.div_euclid(v.0);
let w = (u.0 - q * v.0, u.1 - q * v.1);
(u, v) = (v, w);
}
if v.1 < 0 { (-v.0, -v.1) } else { v }
}
}
impl<M> std::fmt::Display for ModInt<M> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
impl<M: Modulus> std::fmt::Debug for ModInt<M> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let (num, denom) = self.to_rational();
if denom == 1 {
write!(f, "{num}")
} else {
write!(f, "{num}/{denom}")
}
}
}
impl<M: Modulus> std::str::FromStr for ModInt<M> {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let value = s.parse::<u32>()?;
Ok(Self::new(value))
}
}
macro_rules! impl_from_integer {
($($ty:tt),*) => {
$(impl < M : Modulus > From <$ty > for ModInt < M > { fn from(value :
$ty) -> ModInt < M > { Self::new_unchecked(value
.rem_euclid(Self::modulus() as $ty) as u32) } })*
};
}
impl_from_integer!(u32, u64, usize, i32, i64, isize);
impl<M: Modulus> std::ops::Neg for ModInt<M> {
type Output = Self;
fn neg(mut self) -> Self::Output {
if self.val > 0 {
self.val = Self::modulus() - self.val;
}
self
}
}
impl<M: Modulus, T: Into<ModInt<M>>> AddAssign<T> for ModInt<M> {
fn add_assign(&mut self, rhs: T) {
self.val += rhs.into().val;
if self.val >= Self::modulus() {
self.val -= Self::modulus();
}
}
}
impl<M: Modulus, T: Into<ModInt<M>>> SubAssign<T> for ModInt<M> {
fn sub_assign(&mut self, rhs: T) {
self.val = self.val.wrapping_sub(rhs.into().val);
if self.val > Self::modulus() {
self.val = self.val.wrapping_add(Self::modulus());
}
}
}
impl<M: Modulus, T: Into<ModInt<M>>> MulAssign<T> for ModInt<M> {
fn mul_assign(&mut self, rhs: T) {
self.val =
((self.val as u64 * rhs.into().val as u64) % Self::modulus() as u64) as u32;
}
}
impl<M: Modulus, T: Into<ModInt<M>>> DivAssign<T> for ModInt<M> {
#[allow(clippy::suspicious_op_assign_impl)]
fn div_assign(&mut self, rhs: T) {
*self *= rhs.into().inv();
}
}
macro_rules! forward_ops {
($op:ident, $fn:ident, $op_assign:ident, $fn_assign:ident) => {
impl<M: Modulus, T: Into<ModInt<M>>> $op<T> for ModInt<M> {
type Output = ModInt<M>;
fn $fn(mut self, rhs: T) -> ModInt<M> {
self.$fn_assign(rhs);
self
}
}
impl<M: Modulus> $op<&ModInt<M>> for ModInt<M> {
type Output = ModInt<M>;
fn $fn(self, rhs: &ModInt<M>) -> ModInt<M> {
self.$fn(*rhs)
}
}
impl<M: Modulus, T: Into<ModInt<M>>> $op<T> for &ModInt<M> {
type Output = ModInt<M>;
fn $fn(self, rhs: T) -> ModInt<M> {
(*self).$fn(rhs)
}
}
impl<M: Modulus> $op<&ModInt<M>> for &ModInt<M> {
type Output = ModInt<M>;
fn $fn(self, rhs: &ModInt<M>) -> ModInt<M> {
(*self).$fn(*rhs)
}
}
impl<M: Modulus> $op_assign<&ModInt<M>> for ModInt<M> {
fn $fn_assign(&mut self, rhs: &ModInt<M>) {
*self = self.$fn(*rhs);
}
}
};
}
forward_ops!(Add, add, AddAssign, add_assign);
forward_ops!(Sub, sub, SubAssign, sub_assign);
forward_ops!(Mul, mul, MulAssign, mul_assign);
forward_ops!(Div, div, DivAssign, div_assign);
impl<M: Modulus> std::iter::Sum for ModInt<M> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::zero(), Add::add)
}
}
impl<'a, M: Modulus> std::iter::Sum<&'a ModInt<M>> for ModInt<M> {
fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
iter.fold(Self::zero(), Add::add)
}
}
impl<M: Modulus> std::iter::Product for ModInt<M> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::one(), Mul::mul)
}
}
impl<'a, M: Modulus> std::iter::Product<&'a ModInt<M>> for ModInt<M> {
fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
iter.fold(Self::one(), Mul::mul)
}
}
}
}