結果

問題 No.2206 Popcount Sum 2
ユーザー vjudge1
提出日時 2025-08-02 17:49:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 605 ms / 4,000 ms
コード長 3,507 bytes
コンパイル時間 3,075 ms
コンパイル使用メモリ 283,212 KB
実行使用メモリ 11,084 KB
最終ジャッジ日時 2025-08-02 17:50:09
合計ジャッジ時間 12,400 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
bool ST;
namespace FastIO
{
#ifdef ONLINE_JUDGE
    char IN[1<<20],*inS=IN,*inT=IN;
    #define getchar() inS==inT&&(inT=(inS=IN)+fread(IN,1,1<<20,stdin),inS==inT)?EOF:*inS++
    char OUT[1<<20],*outS=OUT;
    #define putchar(x) (outS-OUT==1<<20?fwrite(OUT,1,1<<20,stdout),outS=OUT,0:0,*outS++=x)
    struct Writer{~Writer(){fwrite(OUT,1,outS-OUT,stdout);}}Writ;
#endif
    template<typename T> inline void read(T &x)
    {
        x=0;short f=1;char ch=getchar();
        for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
        for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        x=~f?x:-x;
    }
    inline void read(char &ch){ch=getchar();for(;ch=='\n'||ch==' ';ch=getchar());}
    inline void read(char s[])
    {
        int len=0;char ch=getchar();
        for(;ch=='\n'||ch==' ';ch=getchar());
        for(;ch!='\n'&&ch!=' '&&ch!='\r'&&ch!=EOF;ch=getchar()) s[++len]=ch;
        s[++len]='\0';
    }
    template<typename T> inline void write(T x)
    {
        static char s[105];int top=0;
        do s[top++]=x%10+'0',x/=10;while(x);
        for(;top;) putchar(s[--top]);
    }
    inline void write(const char* s){for(int i=0;s[i]!='\0';i++)putchar(s[i]);}
    template<typename T> inline void print(T x,char ch='\n')
    {
        if(is_same<char,T>::value) putchar(x);
        else{if(x<0)putchar('-'),x=-x;write(x);}
        if(ch!=' '&&ch!='\n'&&ch!='\0') putchar(' ');
        putchar(ch);
        if(ch!=' '&&ch!='\n'&&ch!='\0') putchar('\n');
    }
    inline void print(const char* s,char ch='\n'){write(s);putchar(ch);}
    template<typename T,typename... Args> inline void read(T &x,Args&... args){read(x);read(args...);}
    template<typename T,typename... Args> inline void print(T x,Args... args){print(x,' ');print(args...);}
}
using namespace FastIO;
constexpr int N=2e5+5,B=448,mod=998244353;
namespace math
{
	#define T(x,y) x=(x+(y))%mod
	#define S(x,y) (1ll*(x)*(y)%mod)
	int fac[N],inv[N];
	int power(int x,int y)
	{
		int res=1;
		for(;y;y>>=1,x=S(x,x))
			if(y&1) res=S(res,x);
		return res;
	}
	void prework(int n)
	{
        for(int i=fac[0]=1;i<=n;i++) fac[i]=S(fac[i-1],i);
        inv[n]=power(fac[n],mod-2);
        for(int i=n-1;i>=0;i--) inv[i]=S(inv[i+1],i+1);
    }
	int C(int x,int y){return x<y?0:S(fac[x],S(inv[y],inv[x-y]));}
}
using namespace math;
namespace Junounly
{
	int inv2,Q,n=1,m=1,res[N],id[N],ans=1;
	struct node{int n,m,id;}q[N];
	void addn(int x){ans=(S(ans,2)+mod-C(x-2,m-1))%mod;}
	void deln(int x){ans=S((ans+C(x-2,m-1))%mod,inv2);}
	void addm(int x){T(ans,C(n-1,x-1));}
	void delm(int x){T(ans,mod-C(n-1,x-1));}
    void main()
    {
        read(Q);prework(2e5);inv2=power(2,mod-2);
        for(int i=1;i<=Q;i++) read(q[i].n,q[i].m),q[i].id=i;
        for(int i=1;i<=2e5;i++) id[i]=i/B;
        sort(q+1,q+Q+1,[](node x,node y){return id[x.n]==id[y.n]?(id[x.n]&1?x.m>y.m:x.m<y.m):id[x.n]<id[y.n];});
        for(int i=1;i<=Q;i++)
        {
        	for(;n<q[i].n;) addn(++n);
        	for(;n>q[i].n;) deln(n--);
        	for(;m<q[i].m;) addm(++m);
        	for(;m>q[i].m;) delm(m--);
        	res[q[i].id]=S((power(2,q[i].n)+mod-1)%mod,ans);
        }
        for(int i=1;i<=Q;i++) print(res[i]);
    }
}
bool ED;
int main()
{
#ifdef ONLINE_JUDGE
    Junounly::main();
#else
    double st=clock();
    Junounly::main();
    double ed=clock();
    cerr<<endl;
    cerr<<"Time: "<<ed-st<<" ms\n";
    cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
#endif
    return 0;
}
0