結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-05 11:42:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,828 bytes
コンパイル時間 2,003 ms
コンパイル使用メモリ 199,192 KB
実行使用メモリ 28,984 KB
最終ジャッジ日時 2025-08-05 11:43:07
合計ジャッジ時間 11,481 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
long long l,r,n,m,k,s=1,x,y,b[200100],pw[500100],d[500100],po[500100],mo=998244353;
struct jg
{
    long long l,r,z;
}c[200100];
bool cp(jg a,jg w)
{
    if(b[a.l]==b[w.l])
    {
        return a.r<w.r;
    }
    return b[a.l]<b[w.l];
}
long long p(long long x,long long y)
{
    long long s=1;
    for(;y>0;y=y/2)
    {
        if(y&1)
        {
            s=(s*x)%mo;
        }
        x=(x*x)%mo;
    }
    return s;
}
long long A(long long x,long long y)
{
	if(x<y)
	{
		return 0;
	}
    return (po[x]*pw[x-y])%mo;
}
long long C(long long x,long long y)
{
	if(x<y)
	{
		return 0;
	}
    return (((po[x]*pw[x-y])%mo)*pw[y])%mo;
}
void adr()
{
	s=(s+C(l,r))%mo;
}
void adl()
{
	s=(s*2-C(l,r)+mo)%mo;
}
void jil()
{
	s=((s+C(l,r))*p(2,mo-2))%mo;
}
void jir()
{
	s=(s-C(l,r)+mo)%mo;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    n=200000;
    po[0]=pw[0]=po[1]=pw[1]=1;
    for(long long i=2;i<=n;i++)
    {
        po[i]=(po[i-1]*i)%mo;
    }
	pw[n]=p(po[n],mo-2);
	for(long long i=n-1;i>1;i--)
	{
		pw[i]=pw[i+1]*(i+1)%mo;
	}
	cin>>m;
    k=n/sqrt(m);
    k=max(k,1ll);
    for(int i=1;i<=n;i++)
    {
        b[i]=(i-1)/k+1;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>c[i].l>>c[i].r;
        c[i].l--;
        c[i].r--;
        c[i].z=i;
    }
    sort(c+1,c+m+1,cp);
    l=0;
    r=0;
    s=1;
    for(int i=1;i<=m;i++)
    {
        for(;l<c[i].l;l++)
        {
            adl();
        }
        for(;r>c[i].r;r--)
        {
            jir();
        }
        for(;l>c[i].l;)
        {
            l--;
            jil();
        }
        for(;r<c[i].r;)
        {
			r++;
            adr();
        }
        d[c[i].z]=s*(p(2,c[i].l+1)-1)%mo;
    }
    for(int i=1;i<=m;i++)
    {
        cout<<d[i]<<"\n";
    }
    return 0;
}
0