結果

問題 No.2206 Popcount Sum 2
ユーザー tokitsukaze
提出日時 2025-02-18 21:11:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,406 ms / 4,000 ms
コード長 1,530 bytes
コンパイル時間 2,142 ms
コンパイル使用メモリ 194,020 KB
実行使用メモリ 353,148 KB
最終ジャッジ日時 2025-02-18 21:12:08
合計ジャッジ時間 30,340 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:83:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |         scanf("%d",&T);
      |         ~~~~~^~~~~~~~~
main.cpp:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |                 scanf("%d%d",&n,&m);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int MAX=2e5+10;
ll qpow(ll a,ll b)
{
    ll res=1;
    while(b>0)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll inv(ll x){return qpow(x,mod-2);}
int fac[MAX],invfac[MAX];
void init_comb(int n)
{
    assert(n<MAX);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    invfac[n]=inv(fac[n]);
    for(int i=n-1;~i;i--) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
}
ll C(int n,int m)
{
    if(m>n||m<0||n<0) return 0;
    return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
ll A(int n,int m)
{
    if(m>n||m<0||n<0) return 0;
    return 1ll*fac[n]*invfac[n-m]%mod;
}
struct binomial_prefix_sum
{
    static const int B=450;
    int table[MAX/B+1][MAX];
    void init(int n)
    {
        int i,j;
        init_comb(n);
        for(i=0;i*B<=n;i++)
        {
            table[i][0]=1;
            for(j=1;j<=n;j++)
            {
                table[i][j]=table[i][j-1]+C(i*B,j);
                if(table[i][j]>=mod) table[i][j]-=mod;
            }
        }
    }
    ll get_sum(int n,int m)
    {
        int now=n/B;
        ll res=table[now][m];
        now*=B;
        while(now<n)
        {
            res=2LL*res-C(now,m);
            if(res>=mod) res-=mod;
            else if(res<0) res+=mod;
            now++;
        }
        return res;
    }
}binomsum;
/*
f(n,m)=sum{C(n,k=0..m)}
f(n+1,m)=2*f(n,m)-C(n,m)
O(n sqrt n) - O(sqrt n)
binomsum.init(n);
binomsum.get_sum(n,m); -> sum{C(n,k=0..m)}
*/
int main()
{
    binomsum.init(2e5);
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",(qpow(2,n)-1+mod)
                *binomsum.get_sum(n-1,m-1)%mod);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0