QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#239912#6184. Atcoder ProblemCrysflyAC ✓71ms8648kbC++173.3kb2023-11-05 00:28:132023-11-05 00:28:13

Judging History

你现在查看的是最新测评结果

  • [2023-11-05 00:28:13]
  • 评测
  • 测评结果:AC
  • 用时:71ms
  • 内存:8648kb
  • [2023-11-05 00:28:13]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline ll read()
{
    char c=getchar();ll x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 200005
#define inf 0x3f3f3f3f

ll n,m,x;
modint res[maxn];
modint dp[64][2][2];
map<ll,modint>mp;

modint f[maxn],sf[2];
void calc(modint w,modint a,modint b){
	// w*(1/(1+x))^a*(1/(1-x))^b
	if(!w.x)return;
//	cout<<"calc "<<w.x<<" "<<a.x<<"\n";
	f[0]=w;
	sf[0]=w,sf[1]=0;
	For(i,0,n-1){
		f[i+1]=b*(sf[0]+sf[1])-a*(sf[i%2]-sf[(i+1)%2]);
		f[i+1]*=iv[i+1];
		sf[(i+1)%2]+=f[i+1];
	}
	For(i,0,n)res[i]+=f[i],f[i]=0;
}

signed main()
{
	n=read(),m=read(),x=read(),++m;
	initC(n+1);
	dp[61][0][0]=1;
	mp[0]+=1;
	Rep(i,60,0){
		For(a,0,1)
			For(b,0,1)
				dp[i][a^(m>>i&1)][b^(x>>i&1)]+=dp[i+1][a][b];
		For(a,0,1){
			ll cnt=0;
			Rep(j,60,i+1)
				if(m>>j&1) cnt+=1ll<<(j-1);
			Rep(j,i,0)
				if((m>>j&1) && (a!=(j==i))) cnt+=1ll<<j;
		//	cout<<"cnt "<<i<<" "<<a<<" "<<cnt<<"\n";
			mp[cnt]+=dp[i][a][0]-dp[i][a][1];
		}
		For(a,0,1)
			For(b,0,1)
				dp[i][a][b]+=dp[i+1][a][b];
	}
	for(auto [x,y]:mp) calc(y,x%mod,(m-x)%mod);
	modint I=1; I/=((1ll<<61)%mod);
	For(i,1,n) res[i]*=I,cout<<res[i].x<<"\n";
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6668kb

input:

5 6 7

output:

0
3
7
25
49

result:

ok 5 number(s): "0 3 7 25 49"

Test #2:

score: 0
Accepted
time: 1ms
memory: 6696kb

input:

10 100 0

output:

1
101
1418
38280
756912
13403840
203823022
755806367
368916768
79402702

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 7ms
memory: 8580kb

input:

100000 1152921504606846975 1135906340197086405

output:

1
840200159
757208156
45079381
234857894
778713378
157653094
401709782
230628443
430324215
684650792
138395965
762802417
682389935
242725537
447284705
699422690
810878852
984774439
636218249
418883769
680950647
354420417
642906873
685645540
223359490
370171153
594906335
423999750
963169862
122670093...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 71ms
memory: 8496kb

input:

100000 1135906340197086405 0

output:

1
113027812
695077004
213731896
525802203
335155205
835852454
274346456
475280537
201443359
582037369
724576833
696494373
854514319
826907652
9179469
991556563
422731810
822598649
760659125
311818894
452007631
425590283
442774158
843151305
635490300
6982067
766134056
733977525
692498660
973160682
71...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 11ms
memory: 8648kb

input:

100000 1135906340197086405 1152921504606846975

output:

0
271072006
745954500
176515717
442855562
179056346
723923577
507918653
449150776
606758112
658684747
769476797
90012324
921104758
155944588
921730658
825936439
276825694
210555233
558400169
132510433
973023753
41449997
284153662
633262134
921817216
556971594
428704872
848487910
57553970
402713586
8...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 8608kb

input:

100000 135906340197086405 1152921504606846975

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 7ms
memory: 8608kb

input:

100000 1135906340197086405 38986989798615317

output:

1
271072006
695077004
176515717
525802203
179056346
835852454
507918653
475280537
606758112
582037369
769476797
696494373
921104758
826907652
921730658
991556563
276825694
822598649
558400169
311818894
973023753
425590283
284153662
843151305
921817216
6982067
428704872
733977525
57553970
973160682
8...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 11ms
memory: 8516kb

input:

99999 1152921504606846975 0

output:

1
682155965
757208156
402935458
234857894
302130892
157653094
717810642
230628443
15486544
684650792
745177033
762802417
294962385
242725537
281332463
699422690
669053148
984774439
572399878
418883769
788259891
354420417
872769360
685645540
776292040
370171153
30078222
423999750
253213607
122670093
...

result:

ok 99999 numbers