結果

問題 No.2206 Popcount Sum 2
コンテスト
ユーザー vjudge1
提出日時 2025-08-02 20:00:43
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 930 ms / 4,000 ms
コード長 1,966 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,679 ms
コンパイル使用メモリ 166,496 KB
実行使用メモリ 16,412 KB
最終ジャッジ日時 2025-08-02 20:00:57
合計ジャッジ時間 13,354 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int read()’:
main.cpp:14:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |     scanf("%lld", &x); return x;
      |     ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define LL long long
typedef pair<int,int> PII;
char buf[1 << 21], *p1 = buf, *p2 = buf;
char gc(){
    if(p1 == p2)p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin);
    return *(p1) ++;
}
LL read(){
    LL x = 0, s = 1;
    scanf("%lld", &x); return x;
    char ch = gc();
    while(ch < '0' || ch > '9')s = ch == '-' ? -1 : s, ch = gc();
    while('0' <= ch && ch <= '9')x = (x << 1ll) + (x << 3ll) + (ch ^ 48), ch = gc();
    return x * s;
}

const int N = 2e5 + 10;
const int B = 450;
const int mod = 998244353;

int q;
struct que{int n, m, id; }qu[N];

int ans[N];
bool cmpq(que x, que y){
    if(x.n / B != y.n / B)return x.n / B < y.n / B;
    return x.m < y.m;
}

int fac[N], inv[N], pw2[N], iv2;
int qpw(int d, int u){
    int res = 1;
    while(u){
        if(u & 1)res = res * d % mod;
        d = d * d % mod; u >>= 1;
    }
    return res;
}
void pre(){
    fac[0] = inv[0] = pw2[0] = 1; iv2 = qpw(2, mod - 2);
    for(int i = 1; i <= N - 5; i ++)fac[i] = fac[i - 1] * i % mod, inv[i] = qpw(fac[i], mod - 2), pw2[i] = pw2[i - 1] * 2ll % mod;
}
int C(int x, int y){return y > x ? 0 : fac[x] * inv[y] % mod * inv[x - y] % mod; }

void solve(int qid){
    q = read();
    for(int i = 1; i <= q; i ++)qu[i] = {read(), read(), i};

    sort(qu + 1, qu + 1 + q, cmpq);
    int x = 0, y = 0, gta = 1;
    for(int i = 1; i <= q; i ++){
        int qx = qu[i].n - 1, qy = qu[i].m - 1;
        while(x < qx)gta = gta * 2ll % mod, gta = (gta - C(x, y) + mod) % mod, x ++;
        while(y < qy)gta = (gta + C(x, y + 1)) % mod, y ++;
        while(qy < y)gta = (gta - C(x, y) + mod) % mod, y --;
        while(qx < x)gta = (gta + C(x - 1, y)) % mod, gta = gta * iv2 % mod, x --;
        ans[qu[i].id] = gta * (pw2[qu[i].n] - 1 + mod) % mod;
    }

    for(int i = 1; i <= q; i ++)printf("%lld\n", ans[i]);
}
signed main(){
    pre();
    int qii = 1;
    for(int z = 1; z <= qii; z ++)solve(z);
}
0