codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1350.md (16246B)


      1 Source: https://codeforces.com/blog/entry/77284
      2 
      3 You can view Chinese editorial here: <https://www.luogu.com.cn/blog/Caro23333/codeforces-round-641-zhong-wen-ti-xie>
      4 
      5 Div2.A Problem and editorial by [BlueSmoke](/profile/BlueSmoke "Candidate Master BlueSmoke")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include <iostream>
     15 #include <cstdio>
     16 #include <cstring>
     17 #include <cstdlib>
     18 #include <algorithm>
     19 
     20 using namespace std;
     21 
     22 int main()
     23 {
     24 	int T;
     25 	cin >> T;
     26 	while(T--)
     27 	{
     28 		int n,k;
     29 		cin >> n >> k;
     30 		if(n%2==0)
     31 		{
     32 			cout << n+2*k << endl;
     33 			continue;
     34 		}
     35 		int p = 0;
     36 		for(int i = n; i>=2; i--)
     37 			if(n%i==0)
     38 		    	p = i;
     39 		cout << n+p+2*(k-1) << endl;
     40 	}
     41 	return 0;
     42 }
     43 ```
     44 
     45 Div2.B Problem and editorial by [BlueSmoke](/profile/BlueSmoke "Candidate Master BlueSmoke")
     46 
     47 **Editorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Code**
     52 
     53 ```
     54 #include <iostream>
     55 #include <cstdlib>
     56 #include <cstdio>
     57 #include <cstring>
     58 #include <algorithm>
     59 
     60 using namespace std;
     61 const int MAXN = 500005;
     62 inline int readint()
     63 {
     64 	int res = 0;
     65 	char c = 0;
     66 	while(!isdigit(c))
     67 		c = getchar();
     68 	while(isdigit(c))
     69 		res = res*10+c-'0', c = getchar();
     70 	return res;	
     71 }
     72 int n,a[MAXN],f[MAXN];
     73 
     74 int main()
     75 {
     76 	int T = readint();
     77 	while(T--)
     78 	{
     79 		n = readint();
     80 		for(int i = 1; i<=n; i++)
     81 			a[i] = readint();
     82 		for(int i = 1; i<=n; i++)
     83 			f[i] = 1;
     84 		for(int i = 1; i<=n; i++) 
     85 			for(int j = i*2; j<=n; j += i)
     86 				if(a[i]<a[j])
     87 					f[j] = max(f[j],f[i]+1);
     88 		int ans = 0;
     89 		for(int i = 1; i<=n; i++)
     90 			ans = max(ans,f[i]);
     91 		cout << ans << endl;
     92 	}
     93 	return 0;
     94 }
     95 ```
     96 
     97 Div1.A Problem and editorial by [mydiplomacy](/profile/mydiplomacy "Candidate Master mydiplomacy")
     98 
     99 **Editorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Code**
    104 
    105 ```
    106 #include <iostream>
    107 #include <cstdio>
    108 
    109 using namespace std;
    110 typedef long long ll;
    111 
    112 const int maxn=100005;
    113 
    114 int n;
    115 ll a[maxn];
    116 
    117 ll pre[maxn],suf[maxn];
    118 
    119 ll gcd(ll x, ll y)
    120 {
    121 	if(y==0) return x;
    122 	else return gcd(y,x%y);
    123 }
    124 
    125 ll ga,ans;
    126 
    127 int main()
    128 {
    129 	scanf("%d",&n);
    130 	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    131 	pre[1]=a[1]; suf[n]=a[n];
    132 	for(int i=2;i<=n;i++)
    133 		pre[i]=gcd(pre[i-1],a[i]);
    134 	for(int i=n-1;i>=1;i--)
    135 		suf[i]=gcd(suf[i+1],a[i]);
    136 	for(int i=0;i<=n-1;i++)
    137 	{
    138 		if(i==0)
    139 			ans=suf[2];
    140 		else if(i==n-1)
    141 			ans=ans*pre[n-1]/gcd(pre[n-1],ans);
    142 		else
    143 			ans=ans*gcd(pre[i],suf[i+2])/gcd(gcd(pre[i],suf[i+2]),ans);
    144 	}
    145 	printf("%lld\n",ans);
    146 	return 0;
    147 }
    148 ```
    149 
    150 Div1.B Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.")
    151 
    152 **Editorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Code**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 using namespace std;
    161 typedef long long ll;
    162 typedef unsigned long long ull;
    163 typedef pair<int,int> pii;
    164 #define x first
    165 #define y second
    166 #define mp make_pair
    167 #define pb push_back
    168 template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:TYPE();}
    169 template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:TYPE();}
    170 template <typename TYPE> void readint(TYPE &x)
    171 {
    172     x=0;int f=1;char c;
    173     for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    174     for(;isdigit(c);c=getchar())x=x*10+c-'0';
    175     x*=f;
    176 }
    177 const int MAXN=500005;
    178 
    179 int n,k,a[MAXN];
    180 bool solve()
    181 {
    182 	readint(n),readint(k);
    183 	bool flag=0;
    184 	for(int i=1;i<=n;++i)
    185 	{
    186 		readint(a[i]);
    187 		if(a[i]<k)a[i]=0;
    188 		else if(a[i]>k)a[i]=2;
    189 		else a[i]=1;
    190 		if(a[i]==1)flag=1;
    191 	}
    192 	if(!flag)return 0;
    193 	if(n==1)return 1;
    194 	for(int i=1;i<=n;++i)
    195 		for(int j=i+1;j<=n && j-i<=2;++j)
    196 			if(a[i] && a[j])return 1;
    197 	return 0;
    198 }
    199 
    200 int main()
    201 {
    202 	int T;
    203 	readint(T);
    204 	while(T--)printf(solve()?"yes\n":"no\n");
    205 	return 0;
    206 }
    207 ```
    208 
    209 Div1.C Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.")
    210 
    211 **Editorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Code**
    216 
    217 ```
    218 #include <iostream>
    219 #include <cstdio>
    220 #include <cstring>
    221 #include <cstdlib>
    222 #include <algorithm>
    223 #define pii pair<int,int>
    224 #define mp make_pair
    225 #define fi first
    226 #define se second
    227 
    228 using namespace std;
    229 typedef long long ll;
    230 const int MAXN = 1005;
    231 inline ll readint()
    232 {
    233 	ll res = 0, f = 1;
    234 	char c = 0;
    235 	while(!isdigit(c))
    236 	{
    237 		c = getchar();
    238 		if(c=='-')
    239 			f = -1;
    240 	}
    241 	while(isdigit(c))
    242 		res = res*10+c-'0', c = getchar();
    243 	return res*f;
    244 }
    245 int n,m,T,a[MAXN][MAXN];
    246 char str[MAXN];
    247 int f[MAXN][MAXN],pos[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    248 bool vis[MAXN][MAXN];
    249 inline bool check(int x, int y)
    250 {
    251 	for(int i = 0; i<4; i++)
    252 	{
    253 		int nx = x+pos[i][0], ny = y+pos[i][1];
    254 		if(a[nx][ny]==a[x][y])
    255 			return true;	
    256 	}
    257 	return false;
    258 }
    259 pii q[MAXN*MAXN];
    260 inline void bfs()
    261 {
    262 	int front = 0, rear = 0;
    263 	for(int i = 1; i<=n; i++)
    264 		for(int j = 1; j<=m; j++)
    265 			if(check(i,j))
    266 				f[i][j] = 0, vis[i][j] = true, q[rear++] = mp(i,j);
    267 	while(front<rear)
    268 	{
    269 		pii now = q[front++];
    270 		for(int i = 0; i<4; i++)
    271 		{
    272 			int nx = now.fi+pos[i][0], ny = now.se+pos[i][1];
    273 			if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])
    274 				continue;
    275 			f[nx][ny] = f[now.fi][now.se]+1;
    276 			vis[nx][ny] = true;
    277 			q[rear++] = mp(nx,ny);
    278 		}
    279 	}
    280 }
    281 
    282 int main()
    283 {
    284 	n = readint(), m = readint(), T = readint();
    285 	memset(a,-1,sizeof(a));
    286 	for(int i = 1; i<=n; i++)
    287 	{
    288 		scanf("%s",str+1);
    289 		for(int j = 1;	j<=m; j++) 
    290 			a[i][j] = str[j]-'0';
    291 	}
    292 	bfs();
    293 	int x,y;
    294 	ll t;
    295 	while(T--)
    296 	{
    297 		x = readint(), y = readint(), t = readint();
    298 		if(vis[x][y])
    299 			printf("%d\n",a[x][y]^(max(0ll,t-f[x][y])&1)); 
    300 		else
    301 			printf("%d\n",a[x][y]);
    302 	}
    303 	return 0;
    304 }
    305 ```
    306 
    307 Div1.D Problem and editorial by [Rebelz](/profile/Rebelz "International Grandmaster Rebelz")
    308 
    309 Part of solution by [Elegia](/profile/Elegia "International Grandmaster Elegia")
    310 
    311 **Editorial**
    312 
    313 Tutorial is loading...
    314 
    315 **Code**
    316 
    317 ```
    318 #include<bits/stdc++.h>
    319 
    320 #define pb push_back
    321 #define mp make_pair
    322 #define fi first
    323 #define se second
    324 
    325 using namespace std;
    326 
    327 typedef long long ll;
    328 typedef unsigned long long ull;
    329 typedef pair<int,int> pii;
    330 typedef pair<ll,ll> pll;
    331 
    332 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
    333 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
    334 
    335 int readint(){
    336 	int x=0,f=1; char ch=getchar();
    337 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    338 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    339 	return x*f;
    340 }
    341 
    342 const int cys=998244353;
    343 int n,m;
    344 ll a[100005],ans[300005];
    345 
    346 ll qpow(ll x,ll p){
    347 	ll ret=1;
    348 	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
    349 	return ret;
    350 }
    351 
    352 int main(){
    353 	n=readint();
    354 	for(int i=1;i<=n;i++) a[i]=readint(),m+=a[i];
    355 	ll invm=qpow(m,cys-2),invn1=qpow(n-1,cys-2);
    356 	for(int i=m;i>=1;i--){
    357 		ll k1=i*invm%cys*invn1%cys,k2=(m-i)*invm%cys;
    358 		ans[i]=(k2*ans[i+1]+1)%cys*qpow(k1,cys-2)%cys;
    359 	}
    360 	for(int i=1;i<=m;i++) ans[i]=(ans[i]+ans[i-1])%cys;
    361 	ll res=0;
    362 	for(int i=1;i<=n;i++) res=(res+ans[m-a[i]])%cys;
    363 	res=(res+cys-ans[m]*(n-1)%cys)%cys;
    364 	printf("%lld\n",res*qpow(n,cys-2)%cys);
    365 	return 0;
    366 }
    367 ```
    368 
    369 Div1.E Problem and editorial by [A.K.E.E.](/profile/A.K.E.E. "International Grandmaster A.K.E.E.")
    370 
    371 **Editorial**
    372 
    373 Tutorial is loading...
    374 
    375 **Code**
    376 
    377 ```
    378 #include <bits/stdc++.h>
    379 using namespace std;
    380 typedef long long ll;
    381 typedef pair<int,ll> pii;
    382 #define x first
    383 #define y second
    384 #define pb push_back
    385 const int MAXN=200005;
    386 
    387 int n,m,cnt;
    388 pii a[MAXN];
    389 bool avis[MAXN];
    390 struct Range
    391 {
    392 	int l,r,type;
    393 	ll val;
    394 	Range(){}
    395 	Range(int l,int r,int type,ll val):l(l),r(r),type(type),val(val){}
    396 }b[MAXN];
    397 
    398 int f[2][MAXN],wh[2][MAXN],res[MAXN];
    399 vector<int> str[2][MAXN];
    400 bool check(ll s,int l,int r)
    401 {
    402 	if(s<=0)return !s && r-l+1>=0;
    403 	ll L=1,R=r-l+1,mid,ans=0;
    404 	while(L<=R)
    405 	{
    406 		mid=(L+R)>>1;
    407 		if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1;
    408 		else R=mid-1;
    409 	}
    410 	return s*2<=(r+r-ans+1)*ans;
    411 }
    412 void modify(ll s,int l,int r,vector<int> &tar,int start)
    413 {
    414 	ll L=1,R=r-l+1,mid,ans=0;
    415 	while(L<=R)
    416 	{
    417 		mid=(L+R)>>1;
    418 		if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1;
    419 		else R=mid-1;
    420 	}
    421 	for(int i=l;i<=r;i++)
    422 		if(ans && (i+i+ans-2)*(ans-1)<=(s-i)*2 && (s-i)*2<=(r+r-ans+2)*(ans-1))
    423 			{--ans,s-=i;tar.pb(1);}
    424 		else tar.pb(0);
    425 }
    426 void update(int i,int ti,int ti_1,int pos,ll d)
    427 {
    428 	if(pos<=f[ti][i])return;
    429 	str[ti][i].clear();
    430 	f[ti][i]=pos;wh[ti][i]=ti_1;
    431 	str[ti][i].pb(1);
    432 	for(int j=f[ti][i]+1;j<=b[i].r;j++)str[ti][i].pb(0);
    433 	modify(d-f[ti][i],b[i].r+1,f[ti_1][i-1]-1,str[ti][i],f[ti][i]);
    434 }
    435 
    436 int main()
    437 {
    438 	#ifndef ONLINE_JUDGE
    439 	//freopen("code.in","r",stdin);
    440 	//freopen("code.out","w",stdout);
    441 	#endif
    442 	scanf("%d",&n);
    443 	for(int i=1;i<=n;i++)
    444 	{
    445 		ll y;
    446 		scanf("%lld",&y);
    447 		if(!y)continue;
    448 		a[++m]=make_pair(n-i+1,y);
    449 		avis[n-i+1]=1;
    450 	}
    451 	if(!m)
    452 	{
    453 		for(int i=1;i<=n;i++)putchar('0');
    454 		return 0;
    455 	}
    456 	sort(a+1,a+m+1);
    457 	b[cnt=1]=Range(a[m].x,a[m].x,2,a[m].y);
    458 	for(int i=m-1;i;i--)
    459 	{
    460 		if(a[i].y==a[i+1].y)b[cnt].l=a[i].x,b[cnt].type=0;
    461 		else if(a[i].y==a[i+1].y-1)b[cnt].l=a[i].x,b[cnt].type=1,b[cnt].val--;
    462 		else b[++cnt]=Range(a[i].x,a[i].x,2,a[i].y);
    463 	}
    464 	b[cnt+1]=Range(-1,-1,0,0);
    465 	bool error=0;
    466 	f[0][0]=-1;f[1][0]=n+1;
    467 	for(int i=1;i<=cnt;i++)
    468 	{
    469 		f[0][i]=f[1][i]=-1;
    470 		for(int t=0;t<=1;t++)
    471 			if(f[t][i-1]>b[i].r)
    472 			{
    473 				if(b[i].type==0 || b[i].type==2)
    474 				{
    475 					ll d=(b[i].val-1)-(b[i-1].val-1+t);
    476 					int pos=-1;
    477 					for(int j=min(b[i].l-1ll,d);j>b[i+1].r;--j)
    478 						if(check(d-j,b[i].r+1,f[t][i-1]-1)){pos=j;break;}
    479 					update(i,0,t,pos,d);
    480 				}
    481 				if(b[i].type==1 || b[i].type==2)
    482 				{
    483 					ll d=b[i].val-(b[i-1].val-1+t);
    484 					if(check(d-b[i].l,b[i].r+1,f[t][i-1]-1))
    485 						update(i,1,t,b[i].l,d);
    486 				}
    487 			}
    488 		if(f[0][i]<0 && f[1][i]<0 && i==cnt && !b[i].type)error=1;
    489 	}
    490 	if(error)
    491 	{
    492 		for(int t=0;t<=1;t++)
    493 			if(f[t][cnt-1]>b[cnt].r)
    494 			{
    495 				ll d=(b[cnt].val-1)-(b[cnt-1].val-1+t);
    496 				int pos=-1;
    497 				for(int j=min((ll)b[cnt].r,d);j>=b[cnt].l;--j)
    498 				{
    499 					if(avis[j])continue;
    500 					if(check(d-j,b[cnt].r+1,f[t][cnt-1]-1)){pos=j;break;}
    501 				}
    502 				update(cnt,0,t,pos,d);
    503 			}
    504 	}
    505 	int cur=(f[1][cnt]>0);
    506 	for(int i=1;i<f[cur][cnt];i++)res[i]=0;
    507 	for(int i=cnt;i>0;i--)
    508 	{
    509 		for(int j=0;j<(int)str[cur][i].size();j++)res[j+f[cur][i]]=str[cur][i][j];
    510 		cur=wh[cur][i];
    511 	}
    512 	for(int i=n;i>0;i--)putchar(res[i]+'0');
    513 	return 0;
    514 }
    515 ```
    516 
    517 Div1.F Problem and editorial by [Rebelz](/profile/Rebelz "International Grandmaster Rebelz")
    518 
    519 Hard version solution by [Elegia](/profile/Elegia "International Grandmaster Elegia")
    520 
    521 **Editorial for easy version**
    522 
    523 Tutorial is loading...
    524 
    525 **Code**
    526 
    527 ```
    528 #include<bits/stdc++.h>
    529 
    530 #define pb push_back
    531 #define mp make_pair
    532 #define fi first
    533 #define se second
    534 
    535 using namespace std;
    536 
    537 typedef long long ll;
    538 typedef unsigned long long ull;
    539 typedef pair<int,int> pii;
    540 typedef pair<ll,ll> pll;
    541 
    542 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
    543 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
    544 
    545 int readint(){
    546 	int x=0,f=1; char ch=getchar();
    547 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    548 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    549 	return x*f;
    550 }
    551 
    552 const int cys=998244353;
    553 int n;
    554 ll fac[5005],inv[5005],d[5005][5005],ans[5005];
    555 
    556 ll qpow(ll x,ll p){
    557 	ll ret=1;
    558 	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
    559 	return ret;
    560 }
    561 
    562 int main(){
    563 	n=readint();
    564 	d[0][0]=fac[0]=inv[0]=1;
    565 	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%cys;
    566 	inv[n]=qpow(fac[n],cys-2);
    567 	for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
    568 	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) d[i][j]=(d[i-1][j-1]*(i-j+1)+d[i-1][j]*j)%cys;
    569 	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i]=(ans[i]+d[j][i]*inv[j])%cys;
    570 	for(int i=1;i<=n;i++) printf("%lld ",ans[i]*fac[n]%cys);
    571 	printf("\n");
    572 	return 0;
    573 }
    574 ```
    575 
    576 **Editorial for hard version**
    577 
    578 Tutorial is loading...
    579 
    580 **Code**
    581 
    582 ```
    583 #include<bits/stdc++.h>
    584 
    585 #define pb push_back
    586 #define mp make_pair
    587 #define fi first
    588 #define se second
    589 
    590 using namespace std;
    591 
    592 typedef long long ll;
    593 typedef unsigned long long ull;
    594 typedef vector<ll> vi;
    595 typedef pair<int,int> pii;
    596 typedef pair<ll,ll> pll;
    597 
    598 template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
    599 template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
    600 
    601 int readint(){
    602 	int x=0,f=1; char ch=getchar();
    603 	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    604 	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    605 	return x*f;
    606 }
    607 
    608 const int cys=998244353,g=3,invg=(cys+1)/3;
    609 int n;
    610 ll ni[200015],fac[200015],inv[200015],tw[200005];
    611 
    612 int mod(int x){return x>=cys?x-cys:x;}
    613 
    614 ll qpow(ll x,ll p){
    615 	ll ret=1;
    616 	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
    617 	return ret;
    618 }
    619 
    620 vi operator+(vi a,vi b){
    621 	vi ret(max(a.size(),b.size()));
    622 	for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+(i<b.size()?b[i]:0));
    623 	return ret;
    624 }
    625 
    626 vi operator-(vi a,vi b){
    627 	vi ret(max(a.size(),b.size()));
    628 	for(int i=0;i<ret.size();i++) ret[i]=mod((i<a.size()?a[i]:0)+cys-(i<b.size()?b[i]:0));
    629 	return ret;
    630 }
    631 
    632 vi operator*(vi a,ll b){
    633 	for(int i=0;i<a.size();i++) a[i]=1ll*a[i]*b%cys;
    634 	return a;
    635 }
    636 
    637 vi operator>>(vi a,int b){
    638 	for(int i=0;i<a.size()-b;i++) a[i]=a[i+b];
    639 	a.resize(a.size()-b);
    640 	return a;
    641 }
    642 
    643 namespace poly{
    644 	int N,l;
    645 	int A[1100000],B[1100000],r[1100000],pre1[20][600000],pre2[20][600000];
    646 	void pre(){
    647 		for(int i=1,r=0;i<(1<<19);i<<=1,r++){
    648 			int w=1,wn=qpow(g,(cys-1)/(i<<1));
    649 			for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre1[r][j]=w;
    650 		}
    651 		for(int i=1,r=0;i<(1<<19);i<<=1,r++){
    652 			int w=1,wn=qpow(invg,(cys-1)/(i<<1));
    653 			for(int j=0;j<i;j++,w=1ll*w*wn%cys) pre2[r][j]=w;
    654 		}
    655 	}
    656 	void ntt(int *A,int N,int f){
    657 		for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
    658 		for(int i=1,r=0;i<N;i<<=1,r++){
    659 			for(int j=0;j<N;j+=(i<<1)){
    660 				for(int k=j;k<j+i;k++){
    661 					int x=A[k],y=1ll*A[k+i]*(f>0?pre1[r][k-j]:pre2[r][k-j])%cys;
    662 					A[k]=mod(x+y); A[k+i]=mod(x+cys-y);
    663 				}
    664 			}
    665 		}
    666 		if(f<0){
    667 			int invn=qpow(N,cys-2);
    668 			for(int i=0;i<N;i++) A[i]=1ll*A[i]*invn%cys;
    669 		}
    670 	}
    671 	void init(int t){
    672 		N=1,l=0;
    673 		for(;N<t;N<<=1) l++;
    674 		for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    675 	}
    676 	void getmul(){
    677 		ntt(A,N,1); ntt(B,N,1);
    678 		for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys;
    679 		ntt(A,N,-1);
    680 	}
    681 	vi mul(vi a,vi b){
    682 		init(a.size()+b.size());
    683 		for(int i=0;i<N;i++) A[i]=i<a.size()?a[i]:0;
    684 		for(int i=0;i<N;i++) B[i]=i<b.size()?b[i]:0;
    685 		getmul();
    686 		vi ret(a.size()+b.size()-1);
    687 		for(int i=0;i<ret.size();i++) ret[i]=A[i];
    688 		return ret;
    689 	}
    690 	vi polyinv(vi a,int l){
    691 		if(l==1) return vi(1,qpow(a[0],cys-2));
    692 		a.resize(l);
    693 		vi b=polyinv(a,(l+1)/2);
    694 		init(l<<1);
    695 		for(int i=0;i<N;i++) A[i]=i<l?a[i]:0;
    696 		for(int i=0;i<N;i++) B[i]=i<(l+1)/2?b[i]:0;
    697 		ntt(A,N,1); ntt(B,N,1);
    698 		for(int i=0;i<N;i++) A[i]=1ll*A[i]*B[i]%cys*B[i]%cys;
    699 		ntt(A,N,-1);
    700 		vi t=b*2;
    701 		t.resize(l);
    702 		for(int i=0;i<l;i++) t[i]=mod(t[i]+cys-A[i]);
    703 		return t;
    704 	}
    705 	vi polydiff(vi a){
    706 		for(int i=0;i<a.size()-1;i++) a[i]=1ll*(i+1)*a[i+1]%cys;
    707 		a.resize(a.size()-1);
    708 		return a;
    709 	}
    710 	vi polyint(vi a){
    711 		a.resize(a.size()+1);
    712 		for(int i=a.size()-1;i>=1;i--) a[i]=1ll*a[i-1]*ni[i]%cys;
    713 		a[0]=0;
    714 		return a;
    715 	}
    716 	vi polyln(vi a,int l){
    717 		return polyint(mul(polydiff(a),polyinv(a,l)));
    718 	}
    719 	vi polyexp(vi a,int l){
    720 		if(l==1) return vi(1,1);
    721 		a.resize(l);
    722 		vi b=polyexp(a,(l+1)/2);
    723 		init(l<<1);
    724 		vi t=mul(b,vi(1,1)-polyln(b,l)+a);
    725 		t.resize(l);
    726 		return t;
    727 	}
    728 	vi polypow(vi a,int l,int k){
    729 		return polyexp(polyln(a,l)*k,l);
    730 	}
    731 }
    732 
    733 vi getans(){
    734 	vi f(0);
    735 	for(int i=0;i<=n+1;i++) f.push_back(inv[i+1]);
    736 	vi tmp=poly::mul(f,poly::polyinv((vi(1,1)-f)>>1,n+1));
    737 	vi tw(0); tw.resize(n);
    738 	for(int i=0;i<n;i++) tw[i]=tmp[i+1];
    739 	vi h(0);
    740 	h.push_back(1),h.push_back(1);
    741 	h=poly::polyinv(poly::polyln(h,n+3)>>1,n+2);
    742 	vi g=poly::polyinv((vi(1,1)-h)>>1,n+1);
    743 	vi ph=poly::polypow(h,n+1,n+1);
    744 	vi t1=poly::mul(g,ph);
    745 	vi tmp1=poly::mul(poly::polydiff(h),ph);
    746 	tmp1.resize(n+1);
    747 	vi tmp2=poly::mul(g,g);
    748 	tmp2.resize(n+1);
    749 	vi t2=poly::mul(tmp1,tmp2);
    750 	for(int i=0;i<n;i++) tw[i]=mod(tw[i]+cys-ni[n+1]*mod(t1[i+1]*(n-i+1)%cys+t2[i+1])%cys);
    751 	for(int i=0;i<n;i++) tw[i]=tw[i]*fac[i]%cys;
    752 	reverse(tw.begin(),tw.end());
    753 	tmp.clear();
    754 	for(int i=0;i<n;i++) tmp.push_back(i&1?cys-inv[i]:inv[i]);
    755 	tw=poly::mul(tw,tmp);
    756 	tw.resize(n);
    757 	reverse(tw.begin(),tw.end());
    758 	return tw;
    759 }
    760 
    761 int main(){
    762 	poly::pre();
    763 	n=readint();
    764 	fac[0]=inv[0]=1;
    765 	for(int i=1;i<=n+5;i++) fac[i]=fac[i-1]*i%cys;
    766 	inv[n+5]=qpow(fac[n+5],cys-2);
    767 	for(int i=n+4;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
    768 	for(int i=1;i<=n+5;i++) ni[i]=inv[i]*fac[i-1]%cys;
    769 	vi res=getans();
    770 	for(int i=0;i<n;i++) printf("%lld ",res[i]*fac[n]%cys*inv[i]%cys);
    771 	printf("\n");
    772 	return 0;
    773 }
    774 ```
    775 
    776 You can also view Div1.F editorial by [Elegia](/profile/Elegia "International Grandmaster Elegia") here: <https://codeforces.com/blog/entry/77280>
    777 
    778 Anyway, hope you like these problems and thank you for participating!