結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-23 10:09:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,030 ms / 4,000 ms
コード長 1,995 bytes
コンパイル時間 1,492 ms
コンパイル使用メモリ 167,880 KB
実行使用メモリ 9,288 KB
最終ジャッジ日時 2025-08-23 10:09:23
合計ジャッジ時間 14,026 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:69:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:73:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   73 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, Base = 131, mod = 998244353;
const int INF = 0x3f3f3f3f;

struct Query
{
    int x, y, id;
} q[N];
int n, len;
int fact[N], infact[N];
int s[N], ans[N];

int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

void init()
{
    fact[0] = 1;
    for (int i = 1; i < N; i ++ )
        fact[i] = (LL)fact[i - 1] * i % mod;
    infact[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i -- )
        infact[i] = (LL)infact[i + 1] * (i + 1) % mod;
    int tmp = 2;
    s[0] = 1;
    for (int i = 1; i < N; i ++ , tmp = tmp * 2 % mod)
        s[i] = (s[i - 1] + tmp) % mod;
}

int C(int b, int a)
{
    if (a > b || a < 0 || b < 0) return 0;
    return (LL)fact[b] * infact[a] % mod * infact[b - a] % mod;
}

bool cmp(Query a, Query b)
{
    if (a.x / len == b.x / len) return a.y < b.y;
    return a.x / len < b.x / len;
}

int modu(LL x)
{
    return (x % mod + mod) % mod;
}

signed main()
{
    // freopen("bigdata.in", "r", stdin);
    // freopen("bigdata.out", "w", stdout);

    init();

    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        q[i] = {b - 1, a - 1, i};
    } 
    len = sqrt(n);
    sort(q + 1, q + 1 + n, cmp);
    int _2 = qmi(2, mod - 2);
    for (int i = 1, l = 0, r = 1, res = 1; i <= n; i ++ )
    {
        int x = q[i].x, y = q[i].y;
        while (l > x) res = modu(res - C(r, l)), l -- ;
        while (l < x) l ++ , res = modu(res + C(r, l));
        while (r > y) r -- , res = (LL)(res + C(r, l)) * _2 % mod;
        while (r < y) r ++ , res = modu((LL)res * 2 - C(r - 1, l));
        ans[q[i].id] = (LL)res * s[y] % mod;
    }
    for (int i = 1; i <= n; i ++ )
        printf("%d\n", ans[i]);

    cerr << clock() << endl;

    return 0;
}
0