結果
| 問題 |
No.2206 Popcount Sum 2
|
| ユーザー |
 vjudge1
|
| 提出日時 | 2025-08-02 15:25:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 643 ms / 4,000 ms |
| コード長 | 14,092 bytes |
| コンパイル時間 | 3,314 ms |
| コンパイル使用メモリ | 283,440 KB |
| 実行使用メモリ | 23,256 KB |
| 最終ジャッジ日時 | 2025-08-02 15:25:47 |
| 合計ジャッジ時間 | 14,504 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 18 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
namespace fast_io
{
template <size_t... Ints>
struct index_sequence
{
using type = index_sequence;
using value_type = size_t;
static std::size_t size() { return sizeof...(Ints); }
};
template <class Sequence1, class Sequence2>
struct merge_and_renumber;
template <size_t... I1, size_t... I2>
struct merge_and_renumber<index_sequence<I1...>, index_sequence<I2...>> : index_sequence<I1..., (sizeof...(I1) + I2)...>
{
};
template <size_t N>
struct make_index_sequence : merge_and_renumber<typename make_index_sequence<N / 2>::type, typename make_index_sequence<N - N / 2>::type>
{
};
template <>
struct make_index_sequence<0> : index_sequence<>
{
};
template <>
struct make_index_sequence<1> : index_sequence<0>
{
};
template <typename Func, typename Tuple, std::size_t... index>
auto apply_helper(Func &&func, Tuple &&tuple, index_sequence<index...>) -> decltype(func(std::get<index>(std::forward<Tuple>(tuple))...)) { return func(std::get<index>(std::forward<Tuple>(tuple))...); }
template <typename Func, typename Tuple>
auto apply(Func &&func, Tuple &&tuple) -> decltype(apply_helper(std::forward<Func>(func), std::forward<Tuple>(tuple), make_index_sequence<std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { return apply_helper(std::forward<Func>(func), std::forward<Tuple>(tuple), make_index_sequence<std::tuple_size<typename std::decay<Tuple>::type>::value>{}); }
namespace type_traits
{
template <class Tp>
constexpr bool is_char_v = std::is_same<Tp, char>::value || std::is_same<Tp, signed char>::value || std::is_same<Tp, unsigned char>::value;
template <class Tp>
constexpr bool is_int_v = (std::is_integral<Tp>::value && std::is_signed<Tp>::value && !is_char_v<Tp>) || std::is_same<Tp, __int128_t>::value;
template <class Tp>
constexpr bool is_uint_v = (std::is_integral<Tp>::value && std::is_unsigned<Tp>::value && !is_char_v<Tp>) || std::is_same<Tp, __uint128_t>::value;
template <class Tp>
using make_uint_t = typename std::conditional_t<(std::is_same<Tp, __int128_t>::value || std::is_same<Tp, __uint128_t>::value), std::common_type<__uint128_t>, typename std::conditional_t<std::is_signed<Tp>::value, std::make_unsigned<Tp>, std::common_type<Tp>>>::type;
}
template <size_t BUFFER_SIZE>
class FastIn
{
using self = FastIn<BUFFER_SIZE>;
protected:
char buffer_[BUFFER_SIZE], *now_ = buffer_, *end_ = buffer_;
FILE *file_;
public:
explicit FastIn(FILE *file = stdin) : file_(file) {}
char fetch() { return now_ == end_ && (end_ = (now_ = buffer_) + fread(buffer_, 1, BUFFER_SIZE, file_), now_ == end_) ? EOF : *(now_)++; }
char visit() { return now_ == end_ && (end_ = (now_ = buffer_) + fread(buffer_, 1, BUFFER_SIZE, file_), now_ == end_) ? EOF : *(now_); }
void set_file(FILE *file)
{
file_ = file;
now_ = end_ = buffer_;
}
bool iseof() { return visit() == EOF; }
template <class Tp, std::enable_if_t<type_traits::is_int_v<Tp>> * = nullptr>
self &read(Tp &n)
{
bool is_neg = false;
char ch = fetch();
while (!isdigit(ch))
{
is_neg |= ch == '-';
ch = fetch();
}
n = 0;
while (isdigit(ch))
{
(n *= 10) += ch & 0x0f;
ch = fetch();
}
if (is_neg)
n = -n;
return *this;
}
template <class Tp, std::enable_if_t<type_traits::is_uint_v<Tp>> * = nullptr>
self &read(Tp &n)
{
char ch = fetch();
while (!isdigit(ch))
ch = fetch();
n = 0;
while (isdigit(ch))
{
(n *= 10) += ch & 0x0f;
ch = fetch();
}
return *this;
}
template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
self &read(Tp &n)
{
while (!isgraph(n = fetch()))
;
return *this;
}
self &read(char *n)
{
char *n_ = n;
while (!isgraph(*n_ = fetch()))
;
while (isgraph(*(++n_) = fetch()))
;
*n_ = '\0';
return *this;
}
self &read(std::string &n)
{
n.clear();
char n_;
while (!isgraph(n_ = fetch()))
;
n.push_back(n_);
while (isgraph(n_ = fetch()))
n.push_back(n_);
return *this;
}
template <class Tp, class Up>
self &read(std::pair<Tp, Up> &p) { return read(p.first).read(p.second); }
template <typename... Ts>
self &read(std::tuple<Ts...> &p)
{
apply([&](Ts &...targs)
{ ((read(targs)), ...); }, p);
return *this;
}
self &getline(char *n)
{
char *n_ = n;
while (!isprint(*n_ = fetch()))
;
while (isprint(*(++n_) = fetch()))
;
*n_ = '\0';
return *this;
}
self &getline(std::string &n)
{
char n_;
while (!isprint(n_ = fetch()))
;
n.push_back(n_);
while (isprint(n_ = fetch()))
n.push_back(n_);
return *this;
}
template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
self &strict_read(Tp &n)
{
n = fetch();
return *this;
}
template <class Tp>
self &operator>>(Tp &val) { return read(val); }
};
template <size_t BUFFER_SIZE, size_t INT_BUFFER_SIZE>
class FastOut
{
using self = FastOut<BUFFER_SIZE, INT_BUFFER_SIZE>;
private:
char int_buffer_[INT_BUFFER_SIZE], *now_ib_ = int_buffer_;
protected:
FILE *file_;
char *now_, buffer_[BUFFER_SIZE];
const char *const end_ = buffer_ + BUFFER_SIZE;
public:
explicit FastOut(FILE *file = stdout) : file_(file), now_(buffer_) {}
self &operator=(const self &rhs)
{
file_ = rhs.file_;
now_ = buffer_ + (rhs.now_ - rhs.buffer_);
memcpy(buffer_, rhs.buffer_, sizeof(*buffer_) * (rhs.now_ - rhs.buffer_));
return *this;
}
FastOut(const self &rhs) { *this = rhs; }
~FastOut() { flush(); }
void flush()
{
fwrite(buffer_, 1, now_ - buffer_, file_);
now_ = buffer_;
}
void rebind(FILE *file) { file_ = file; }
template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
self &write(const Tp &n)
{
if (now_ == end_)
flush();
*(now_++) = n;
return *this;
}
self &write(const char *n)
{
size_t len = strlen(n), l_;
const char *n_ = n;
while (now_ + len >= end_)
{
l_ = end_ - now_;
memcpy(now_, n_, l_);
now_ += l_;
n_ += l_;
len -= l_;
flush();
}
memcpy(now_, n_, len);
now_ += len;
return *this;
}
template <class Tp, std::enable_if_t<type_traits::is_int_v<Tp>> * = nullptr>
self &write(Tp n)
{
if (n < 0)
{
write('-');
n = -n;
}
return write(static_cast<typename type_traits::make_uint_t<Tp>>(n));
}
template <class Tp, std::enable_if_t<type_traits::is_uint_v<Tp>> * = nullptr>
self &write(Tp n)
{
now_ib_ = int_buffer_ + INT_BUFFER_SIZE - 1;
do
{
*(--(now_ib_)) = char(n % 10) | '0';
} while (n /= 10);
return write(now_ib_);
}
self &write(const std::string &str) { return write(str.c_str()); }
template <class Tp, class Up>
self &write(const std::pair<Tp, Up> &p) { return write(p.first).space().write(p.second); }
template <typename... Ts>
self &write(const std::tuple<Ts...> &p)
{
apply([&](Ts const &...targs)
{std::size_t n{0};((write(targs).space_if(++n!=sizeof...(Ts))),...); }, p);
return *this;
}
self &linebreak() { return write('\n'); }
self &linebreak_if(bool flag) { return flag ? linebreak() : *this; }
self &space() { return write(' '); }
self &space_if(bool flag) { return flag ? space() : *this; }
template <class Tp>
self &operator<<(const Tp &val) { return write(val); }
};
const std::size_t BUFFER_SIZE = (1 << 21) + 5;
FastIn<BUFFER_SIZE> fin;
FastOut<BUFFER_SIZE, 21> fout;
};
namespace __LYC__
{
template <typename T>
T lowbit(const T x) { return x & (-x); }
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int tmp = exgcd(b, a % b, x, y);
int tmpx = x;
x = y;
y = tmpx - y * (a / b);
return tmp;
}
int finv(int a, int m)
{
int x, y;
if (exgcd(a, m, x, y) != 1)
return 0;
x %= m;
if (x < 0)
x += m;
return x;
}
template <typename T>
class __value_add_value
{
public:
constexpr T operator()(const T &lhs, const T &rhs) const { return lhs + rhs; }
};
template <typename T>
class maxval
{
public:
constexpr T operator()(const T &lhs, const T &rhs) const { return max(lhs, rhs); }
};
template <typename T>
class minval
{
public:
constexpr T operator()(const T &lhs, const T &rhs) const { return min(lhs, rhs); }
};
template <class T = int, class cmp = __value_add_value<T>>
class BIT
{
public:
int n = 0;
T *c;
BIT(int _n = 0)
{
c = new T[_n + 1];
n = _n;
for (int i = 0; i <= n; i++)
c[i] = T();
}
void update(int x, T k)
{
if (x <= 0)
return;
while (x <= n)
{
c[x] = cmp{}(c[x], k);
x += lowbit(x);
}
}
void init(int _n = -1, T val = T(), T *a = NULL)
{
if (_n != n)
{
delete[] c;
c = new T[_n + 1];
n = _n;
}
for (int i = 0; i <= n; i++)
c[i] = T();
if (a == NULL)
for (int i = 1; i <= n; i++)
update(i, val);
else
for (int i = 1; i <= n; i++)
update(i, a[i]);
}
void clear(T val = T(), T *a = NULL)
{
for (int i = 0; i <= n; i++)
c[i] = T();
if (a == NULL)
for (int i = 1; i <= n; i++)
update(i, val);
else
for (int i = 1; i <= n; i++)
update(i, a[i]);
}
T query(int x)
{
T res = T();
while (x)
{
res = cmp{}(res, c[x]);
x -= lowbit(x);
}
return res;
}
};
};
using __LYC__::finv, __LYC__::exgcd, __LYC__::BIT, __LYC__::maxval, __LYC__::minval, __LYC__::lowbit;
#define rep(l, r, k) for (auto i = (l); i <= (r); i += (k))
//#define int long long
/*
#define cin fast_io::fin
#define cout fast_io::fout
*/
const int N = 1e6, INF = 1e9,P=998244353;
int a[N + 5],b[N+5],fac[N+5],inv[N+5];
long long fpow(long long p,int q){
long long res=1;
while(q){
if(q&1) res=res*p%P;
p=p*p%P;
q>>=1;
}
return res;
}
int C(int x,int y){
if(y<0||x<y) return 0;
return (long long)fac[x]*inv[y]%P*inv[x-y]%P;
}
int q,ans[N+5],s;
struct quesion{
int n,m,id;
friend bool operator<(quesion x,quesion y){
int idx=(x.n+s-1)/s,idy=(y.n+s-1)/s;
if(idx==idy){
if(idx&1) return x.m<y.m;
else return x.m>y.m;
}
return idx<idy;
}
} ques[N+5];
void solve()
{
cin>>q;
s=sqrt(q);
for(int i=1;i<=q;i++){
cin>>ques[i].n>>ques[i].m;
ques[i].n--;
ques[i].m--;
ques[i].id=i;
}
sort(ques+1,ques+q+1);
int n=0,m=0,res=1;
for(int i=1;i<=q;i++){
while(m<ques[i].m){
m++;
res+=C(n,m);
if(res>=P) res-=P;
}
while(ques[i].n<n){
n--;
res=(long long)(res+C(n,m))*inv[2]%P;
}
while(n<ques[i].n){
res=(res<<1)-C(n,m);
if(res<0) res+=P;
if(res>=P) res-=P;
n++;
}
while(ques[i].m<m){
res-=C(n,m);
if(res<0) res+=P;
m--;
}
ans[ques[i].id]=res*(fpow(2,ques[i].n+1)-1ll)%P;
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
signed main()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=N;i++){
fac[i]=(long long)fac[i-1]*i%P;
inv[i]=(long long)(P-P/i)*inv[P%i]%P;
}
for(int i=3;i<=N;i++) inv[i]=(long long)inv[i-1]*inv[i]%P;
int Tcases = 1;
//cin >> Tcases;
while (Tcases--)
solve();
return 0;
}