結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 15:35:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,424 bytes
コンパイル時間 1,335 ms
コンパイル使用メモリ 163,520 KB
実行使用メモリ 14,244 KB
最終ジャッジ日時 2025-08-02 15:35:24
合計ジャッジ時間 8,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:59:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
main.cpp:62:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

const int N = 2e5 + 10, mod = 998244353;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int fact[N], infact[N], p[N], s[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;
    p[0] = 1;
    for (int i = 1; i < N; i ++ )
        p[i] = (LL)p[i - 1] * 2 % mod;
    s[0] = 1;
    for (int i = 1; i < N; i ++ ) 
        s[i] = (s[i - 1] + p[i]) % mod;
} 

int C(int m, int n)
{
    if (!n) return 1;
    if (n > m || n < 0 || m < 0) return 0;
    return (LL)fact[m] * infact[n] % mod * infact[m - n] % mod;
}

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

    init();

    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        int tmp = 0;
        for (int i = 0; i < m; i ++ )
            tmp = (tmp + C(n - 1, i)) % mod;
        int ans = (LL)s[n - 1] * tmp % mod;
        printf("%d\n", ans);
    }

    return 0;
}
0