codeforces-scrape

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

1704.md (19236B)


      1 Source: https://codeforces.com/blog/entry/105464
      2 
      3 Tutorial is loading...
      4 
      5 **solution**
      6 
      7 ```
      8 #include <bits/stdc++.h>
      9 using namespace std;
     10 const int maxn = 2e5;
     11 signed main() {
     12     ios::sync_with_stdio(false);
     13     cin.tie(nullptr);
     14     cout.tie(nullptr);
     15     int T;
     16     cin >> T;
     17     while (T--) {
     18         int n, m;
     19         cin >> n >> m;
     20         string a, b;
     21         cin >> a >> b;
     22         if (n < m) {
     23             cout << "NO\n";
     24             continue;
     25         }
     26         bool same = true;
     27         for (int i = 1; i < b.size(); ++i) {
     28             if (a[i + n - m] != b[i]) {
     29                 same = false;
     30                 break;
     31             }
     32         }
     33         if (!same) {
     34             cout << "NO\n";
     35             continue;
     36         }
     37         for (int i = 0; i < n - m + 1; ++i) {
     38             if (a[i] == b[0]) {
     39                 same = false;
     40             }
     41         }
     42         if (same) {
     43             cout << "NO\n";
     44         }
     45         else {
     46             cout << "YES\n";
     47         }
     48     }
     49 }
     50 ```
     51 
     52 Tutorial is loading...
     53 
     54 **solution**
     55 
     56 ```
     57 #include <stdio.h>
     58 #include <string.h>
     59 #include <vector>
     60 #include <set>
     61 #include <queue>
     62 #include <string>
     63 #include <map>
     64 #include <chrono>
     65 #include <stdlib.h>
     66 #include <time.h>
     67 #include <algorithm>
     68 #include <iostream>
     69 #include <memory>
     70 #include <cstdio>
     71 #include <assert.h>
     72 #include <iostream>
     73 const int MAXN = 300005;
     74 int numbers[MAXN];
     75 int main() {
     76 	int t;
     77 	int n, x;
     78 
     79 	scanf("%d", &t);
     80 	while (t--)
     81 	{
     82 		scanf("%d %d", &n, &x);
     83 		for (int i = 1; i <= n; i++) {
     84 			scanf("%d", &numbers[i]);
     85 		}
     86 		int num_min = numbers[1];
     87 		int num_max = numbers[1];
     88 		int res = 0;
     89 		for (int i = 2; i <= n; i++) {
     90 			if (numbers[i] > num_max) {
     91 				num_max = numbers[i];
     92 			}
     93 			if (numbers[i] < num_min) {
     94 				num_min = numbers[i];
     95 			}
     96 			if (num_max - num_min > 2 * x) {
     97 				res++;
     98 				num_min = num_max = numbers[i];
     99 			}
    100 		}
    101 		printf("%d\n", res);
    102 	}
    103 	return 0;
    104 }
    105 ```
    106 
    107 Tutorial is loading...
    108 
    109 **solution**
    110 
    111 ```
    112 #include<bits/stdc++.h>
    113 using namespace std;
    114 const int N = 500005, inf = 2147483647, M = 1004535809;
    115 int n, m, a[N], T, k;
    116 struct str {
    117 	int x, y;
    118 }t[N];
    119 int main() {
    120 	scanf("%d", &T);
    121 	while (T--) {
    122 		k = 0;
    123 		scanf("%d %d", &n, &m);
    124 		for (int i = 1; i <= m; ++i)
    125 			scanf("%d", &a[i]);
    126 		sort(a + 1, a + 1 + m);
    127 		for (int i = 2; i <= m; ++i)
    128 			t[++k] = { a[i] - a[i - 1] - 1,2 };
    129 		int num_tmp = a[1] + n - a[m] - 1;
    130 		if (num_tmp > 0) {
    131 			t[++k] = { num_tmp, 2 };
    132 		}
    133 		sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; });
    134 		long long ans = 0, cnt = 0;
    135 		for (int i = 1; i <= k; ++i) {
    136 		    if (t[i].x - cnt * 2 > 0) {
    137 		      int num_tmp = max(1ll, t[i].x - cnt * 2 - 1);
    138 			  ans += num_tmp;
    139 		    }
    140 		    cnt += 2;
    141 		}
    142 		printf("%lld\n", n - ans);
    143 	}
    144 }
    145 ```
    146 
    147 Tutorial is loading...
    148 
    149 **solution**
    150 
    151 ```
    152 #include <stdio.h>
    153 #include <string.h>
    154 #include <vector>
    155 #include <map>
    156 #include <cassert>
    157 const int MAXN = 500005;
    158 std::vector<long long> numbers[MAXN];
    159 std::map<long long, long long> val_to_index;
    160 int main()
    161 {
    162 	int t;
    163 	int n, m;
    164 	scanf("%d ", &t);
    165 	while (t--)
    166 	{
    167 		val_to_index.clear();
    168 		scanf("%d %d", &n, &m);
    169 		long long num_tmp;
    170 		for (int i = 1; i <= n; i++) {
    171 		    numbers[i].clear();
    172 		    numbers[i].push_back(0);
    173 			for (int j = 1; j <= m; j++) {
    174 				scanf("%lld", &num_tmp);
    175 				numbers[i].push_back(num_tmp);
    176 			}
    177 		}
    178 		long long res_tmp = -1;
    179 		for (long long i = 1; i <= n; i++) {
    180 			long long val = 0;
    181 			for (long long j = 1; j <= m; j++) {
    182 				val += (j * numbers[i][j]);
    183 			}
    184 			if (val_to_index.find(val) != val_to_index.end()) {
    185 			    res_tmp = val;
    186 				val_to_index[val] = -1;
    187 			}
    188 			else {
    189 				val_to_index[val] = i;
    190 			}
    191 		}
    192 		assert(val_to_index.size() == 2);
    193 		for (auto &item : val_to_index) {
    194 			if (item.second != -1ll) {
    195 				printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first));
    196 				break;
    197 			}
    198 		}
    199 	}
    200 	return 0;
    201 }
    202 ```
    203 
    204 Tutorial is loading...
    205 
    206 **solution**
    207 
    208 ```
    209 #include<bits/stdc++.h>
    210 using namespace std;
    211 const int N = 500005, inf = 2147483647, M = 998244353;
    212 int n, m, a[N], u, v, i, d[N], q[N], r, mx;
    213 int b[N], tmp[N];
    214 vector<int> g[N], z[N];
    215 long long s[N];
    216 int p[15];
    217 void NEX(int M) {
    218 	for (int i = 1; i <= n; ++i)
    219 		if (b[i]) {
    220 			tmp[i] += b[i] - 1;
    221 			for (auto it : g[i])
    222 				++tmp[it];
    223 		}
    224 	for (int i = 1; i <= n; ++i) {
    225 		if (tmp[i] >= M)
    226 			b[i] = tmp[i] % M + M;
    227 		else
    228 			b[i] = tmp[i] % M;
    229 		tmp[i] = 0;
    230 	}
    231 }
    232 int cal(int M) {
    233 	for (int i = 1; i <= n; ++i) {
    234 		b[i] = a[i];
    235 	}
    236 	for (int i = 1; i <= n; ++i) {
    237 		bool fl = false;
    238 		for (int j = 1; j <= n; ++j)
    239 			if (b[j])
    240 				fl = true;
    241 		if (!fl)
    242 			return i - 1;
    243 		NEX(M);
    244 	}
    245 	return n;
    246 }
    247 int main() {
    248 	int t;
    249 	scanf("%d", &t);
    250 	while (t--) {
    251 		scanf("%d %d", &n, &m);
    252 		for (int i = 1; i <= n; ++i) {
    253 			scanf("%d", &a[i]);
    254 			g[i].clear();
    255 			z[i].clear();
    256 			d[i] = 0;
    257 			tmp[i] = 0;
    258 			s[i] = 0;
    259 		}
    260 		for (int i = 1; i <= m; ++i) {
    261 			scanf("%d %d", &u, &v);
    262 			++d[u];
    263 			g[u].push_back(v);
    264 			z[v].push_back(u);
    265 		}
    266 		mx = cal(M);
    267 		if (mx < n) {
    268 			cout << mx << endl;
    269 			continue;
    270 		}
    271 		r = 0;
    272 		for (int i = 1; i <= n; ++i)
    273 			if (!d[i])
    274 				q[++r] = i;
    275 		s[q[1]] = 1;
    276 		for (int i = 1; i <= r; ++i) {
    277 			s[q[i]] %= M;
    278 			for (auto it : z[q[i]]) {
    279 				--d[it];
    280 				s[it] += s[q[i]];
    281 				if (!d[it])
    282 					q[++r] = it;
    283 			}
    284 		}
    285 		long long ans = n;
    286 		for (int i = 1; i <= n; ++i)
    287 			ans = (ans + s[i] * b[i]) % M;
    288 		cout << ans << endl;
    289 	}
    290 }
    291 ```
    292 
    293 Tutorial is loading...
    294 
    295 **solution**
    296 
    297 ```
    298 #include<bits/stdc++.h>
    299 using namespace std;
    300 const int N=500005,inf=2147483647,M=998244353;
    301 int n,i,t,f[N],vis[N];
    302 char c[N];
    303 int main(){
    304     for(int i=1;i<=1000;++i){
    305         for(int j=0;j<=i-2;++j)
    306             vis[f[j]^f[i-2-j]]=1;
    307         int j;
    308         for(j=0;vis[j];++j);
    309         f[i]=j;
    310         for(int j=0;j<=i;++j)
    311             vis[j]=0;
    312     }
    313     for(int i=1001;i<N;++i)
    314         f[i]=f[i-34];
    315     scanf("%d",&t);
    316     while(t--){
    317         scanf("%d",&n);
    318         scanf("%s",c+1);
    319         int s=0;
    320         for(int i=1;i<=n;++i)
    321             if(c[i]=='R')
    322                 ++s;
    323             else
    324                 --s;
    325         if(s>0)
    326             puts("Alice");
    327         if(s<0)
    328             puts("Bob");
    329         if(s==0){
    330             int ans=0;
    331             for(int i=1;i<=n;){
    332                 int j=i+1;
    333                 for(;j<=n&&c[j]!=c[j-1];++j);
    334                     ans^=f[j-i];
    335                 i=j;
    336             }
    337             puts(ans?"Alice":"Bob");
    338         }
    339     }
    340 }
    341 ```
    342 
    343 Tutorial is loading...
    344 
    345 **solution**
    346 
    347 ```
    348 #include<bits/stdc++.h>
    349 using namespace std;
    350 const int M1=998244353,M2=1004535809,M3=469762049,E=524288,N=200005;
    351 struct poly{
    352     const int M;
    353     poly(int _M):M(_M){}
    354     int R[N*4];
    355     long long qpow(long long a,long long b){
    356         long long ans=1;
    357         while(b){
    358             if(b&1)
    359                 ans=ans*a%M;
    360             a=a*a%M;
    361             b>>=1;
    362         }
    363         return ans;
    364     }
    365     long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4];
    366     void init(int E,int g){
    367         int i;
    368         iwn[E/2]=wn[E/2]=1;
    369         long long s1=qpow(g,(M-1)/E);
    370         long long s2=qpow(s1,M-2);
    371         for(i=E/2+1;i<E;++i){
    372             wn[i]=wn[i-1]*s1%M;
    373             iwn[i]=iwn[i-1]*s2%M;
    374         }
    375         for(i=E/2-1;i;--i){
    376             wn[i]=wn[i<<1];
    377             iwn[i]=iwn[i<<1];
    378         }
    379         ifac[0]=fac[0]=inv[1]=1;
    380         for(i=2;i<E;++i)
    381             inv[i]=inv[M%i]*(M-M/i)%M;
    382         for(i=1;i<E;++i){
    383             ifac[i]=inv[i]*ifac[i-1]%M;
    384             fac[i]=fac[i-1]*i%M;
    385         }
    386     }
    387     unsigned long long ccc[N*4];
    388     void NTT(long long *f,int lim,int op){
    389         int i,j,k;
    390         for(i=0;i<lim;++i){
    391             R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
    392             if(R[i]<i)
    393                 swap(f[R[i]],f[i]);
    394         }
    395         for(i=0;i<lim;++i)
    396             ccc[i]=(f[i]%M+M)%M;
    397         for(i=1;i<lim;i<<=1)
    398             for(j=0;j<lim;j+=(i<<1))
    399                 for(k=j;k<j+i;++k){
    400                     long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
    401                     unsigned long long p=ccc[k+i]*w%M;
    402                     ccc[k+i]=ccc[k]+M-p;
    403                     ccc[k]+=p;
    404                 }
    405         for(i=0;i<lim;++i)
    406             f[i]=ccc[i]%M;
    407         if(op==-1){
    408             long long inv=qpow(lim,M-2);
    409             for(i=0;i<lim;++i)
    410                 f[i]=f[i]*inv%M;
    411         }
    412     }
    413     long long ta[N*4],tb[N*4];
    414     void mult(long long *a,int n,long long *b,int m,long long *c){
    415         int lim=1;
    416         while(lim<n+m)
    417             lim<<=1;
    418         copy(a,a+n,ta);
    419         copy(b,b+m,tb);
    420         for(int i=n;i<lim;++i)
    421             ta[i]=0;
    422         for(int i=m;i<lim;++i)
    423             tb[i]=0;
    424         NTT(ta,lim,1);
    425         NTT(tb,lim,1);
    426         for(int i=0;i<lim;++i)
    427             ta[i]=ta[i]*tb[i]%M;
    428         NTT(ta,lim,-1);
    429         copy(ta,ta+lim,c);
    430     }
    431 }X(M1),Y(M2),Z(M3);
    432 int n,m,o[N],t,tn;
    433 long long a[N],b[N],c[N],d[N*4],e[N],f[N*4],ss[N],td[N],tf[N];
    434 bool fl[N],zz;
    435 vector<int> ans;
    436 long long cal(int l,int r){
    437     return 1ll*(l+r)*(r-l+1)/2;
    438 }
    439 long long cal2(int u,int v){
    440     return 1ll*((v-u)/2+1)*(u+v)/2;
    441 }
    442 bool iok(int n,int p,int q){
    443     long long ss=q+1ll*(n/2)*(n/2+1);
    444     p=p+(n/2+1);
    445     long long mn=cal(0,p-1),mx=cal(n-p+1,n);
    446     if(mn<=ss&&ss<=mx){
    447         for(int i=n;i<n+m-2;++i)
    448             if(td[i]!=tf[i-n+1]&&td[i]!=tf[i-n+1]-1)
    449                 return false;
    450         ss-=mn;
    451         for(int i=n;i<n+m-2;++i)
    452             if(td[i]!=tf[i-n+1])
    453                 ans.push_back(i+2);
    454         fill(fl,fl+1+n,0);
    455         for(int i=0;i<p;++i)
    456             fl[(ss/p+(i>=p-ss%p)+i)]=1;
    457         for(int i=0;i<=n;++i)
    458             if(fl[i]^(i&1)^1)
    459                 if(n+1-i<=tn)
    460                     ans.push_back(n+1-i);
    461         zz=true;
    462         return true;
    463     }
    464     return false;
    465 }
    466 void OT(){
    467     if(!zz)
    468         puts("-1");
    469     else{
    470         printf("%d\n",ans.size());
    471         for(auto it:ans)
    472             printf("%d ",it);
    473         printf("\n");
    474     }
    475 }
    476 void judgement(poly &v,long long *c,long long *e){
    477     for(int i=0;i<n-2;++i)
    478         d[i]=(c[i+1]+c[i+2])%v.M;
    479     for(int i=0;i<m-2;++i)
    480         f[i]=(e[i+1]+e[i+2])%v.M;
    481     reverse(f,f+m-2);
    482     long long s=0;
    483     for(int i=0;i<m-2;++i)
    484         s+=(f[i]*f[i]-f[i])%v.M;
    485     for(int i=1;i<=n-2;++i)
    486         ss[i]=(ss[i-1]+d[i-1]*(d[i-1]+1))%v.M;
    487     v.mult(d,n-2,f,m-2,d);
    488     for(int i=m-3;i<n-2;++i)
    489         if((s+ss[i+1]-ss[i-m+3]-2*d[i])%v.M!=0)
    490             o[i-m+4]=0;
    491 }
    492 int main(){
    493     X.init(E,3);
    494     Y.init(E,3);
    495     Z.init(E,3);
    496     scanf("%d",&t);
    497     while(t--){
    498         scanf("%d",&n);
    499         tn=n;
    500         for(int i=1;i<=n;++i)
    501             scanf("%lld",&a[i]);
    502         scanf("%d",&m);
    503         for(int i=1;i<=m;++i)
    504             scanf("%lld",&b[i]);
    505         for(int i=1;i<n;++i)
    506             c[i]=a[i]+a[i+1];
    507         for(int i=1;i<m;++i)
    508             e[i]=b[i]+b[i+1];
    509         fill(o,o+1+n,0);
    510         ans.clear();
    511         for(int i=1;i<=n;++i)
    512             o[i]=1;
    513         if(m>2){
    514             for(int i=0;i<n-2;++i)
    515                 td[i+1]=c[i+1]+c[i+2];
    516             for(int i=0;i<m-2;++i)
    517                 tf[i+1]=e[i+1]+e[i+2];
    518             judgement(X,c,e);
    519             judgement(Y,c,e);
    520             judgement(Z,c,e);
    521         }
    522         else
    523             for(int i=1;i<=n;++i)
    524                 o[i]=1;
    525         int x=-1;
    526         zz=false;
    527         if(m==1){
    528             for(int i=1;i<=n;++i)
    529                 if(-cal2(0,i/2*2)<=b[1]-a[i]&&b[1]-a[i]<=cal2(1,(i-1)/2*2+1)){
    530                     for(int j=-(i/2+1);j<=(i+1)/2;++j)
    531                         if(iok(i,j,b[1]-a[i]))
    532                             break;
    533                     break;
    534                 }
    535         }
    536         else
    537             for(int i=1;i+m-1<=n;++i)
    538                 if(o[i]&&iok(i,(a[i]+a[i+1])-(b[1]+b[2]),b[1]-a[i]))
    539                     break;
    540         OT();
    541     }
    542 }
    543 ```
    544 
    545 Tutorial is loading...
    546 
    547 **solution**
    548 
    549 ```
    550 #include<bits/stdc++.h>
    551 using namespace std;
    552 const int N=200005,E=15000005;
    553 const long long inf=1000000000000000000ll;
    554 int n,M,mi[5005][5005];
    555 long long fac[N],inv[N],ans;
    556 long long C(int n,int m){
    557     return fac[n]*inv[m]%M*inv[n-m]%M;
    558 }
    559 long long qpow(long long a,long long b){
    560     long long s=a,ans=1;
    561     while(b){
    562         if(b&1)
    563             ans=ans*s%M;
    564         s=s*s%M;
    565         b>>=1;
    566     }
    567     return ans;
    568 }
    569 int main(){
    570     cin>>n>>M;
    571     fac[0]=inv[0]=inv[1]=1;
    572     for(int i=2;i<=n;++i)
    573         inv[i]=inv[M%i]*(M-M/i)%M;
    574     for(int i=1;i<=n;++i){
    575         inv[i]=inv[i-1]*inv[i]%M;
    576         fac[i]=fac[i-1]*i%M;
    577     }
    578     long long s1=1;
    579     for(int i=0;i<=n;++i){
    580         mi[i][0]=1;
    581         for(int j=1;j<=n;++j)
    582             mi[i][j]=1ll*mi[i][j-1]*i%M;
    583     }
    584     for(int j=1;2*j<=n;++j){
    585         s1=s1*(n-1)%M;
    586         for(int i=0;i<=n-2*j;++i)
    587             ans=(ans+C(n,i)*fac[n-i]%M*s1%M*mi[n-i-j][i]%M*C(n-i-j-1,j-1)%M*inv[j])%M;
    588     }
    589     cout<<ans<<endl;
    590 }
    591 ```
    592 
    593 Tutorial is loading...
    594 
    595 **solution**
    596 
    597 ```
    598 #include<bits/stdc++.h>
    599 using namespace std;
    600 const int N=100005,inf=2147483647;
    601 const long long sq5=200717101;
    602 int M;
    603 namespace poly{
    604     int R[N*4];
    605     long long qpow(long long a,long long b){
    606         long long ans=1;
    607         while(b){
    608             if(b&1)
    609                 ans=ans*a%M;
    610             a=a*a%M;
    611             b>>=1;
    612         }
    613         return ans;
    614     }
    615     long long wn[N*4],iwn[N*4],inv[N*4],fac[N*4],ifac[N*4],g;
    616     void init(int E){
    617         int i;
    618         iwn[E/2]=wn[E/2]=1;
    619         long long s1=qpow(g,(M-1)/E);
    620         long long s2=qpow(s1,M-2);
    621         for(i=E/2+1;i<E;++i){
    622             wn[i]=wn[i-1]*s1%M;
    623             iwn[i]=iwn[i-1]*s2%M;
    624         }
    625         for(i=E/2-1;i;--i){
    626             wn[i]=wn[i<<1];
    627             iwn[i]=iwn[i<<1];
    628         }
    629         ifac[0]=fac[0]=inv[1]=1;
    630         for(i=2;i<E;++i)
    631             inv[i]=inv[M%i]*(M-M/i)%M;
    632         for(i=1;i<E;++i){
    633             ifac[i]=inv[i]*ifac[i-1]%M;
    634             fac[i]=fac[i-1]*i%M;
    635         }
    636     }
    637     unsigned long long ccc[N*4];
    638     void NTT(long long *f,int lim,int op){
    639         int i,j,k;
    640         for(i=0;i<lim;++i){
    641             R[i]=(R[i>>1]>>1)|(i&1?lim>>1:0);
    642             if(R[i]<i)
    643                 swap(f[R[i]],f[i]);
    644         }
    645         for(i=0;i<lim;++i)
    646             ccc[i]=(f[i]%M+M)%M;
    647         for(i=1;i<lim;i<<=1)
    648             for(j=0;j<lim;j+=(i<<1))
    649                 for(k=j;k<j+i;++k){
    650                     long long w=(op==1?wn[k-j+i]:iwn[k-j+i]);
    651                     unsigned long long p=ccc[k+i]*w%M;
    652                     ccc[k+i]=ccc[k]+M-p;
    653                     ccc[k]+=p;
    654                 }
    655         for(i=0;i<lim;++i)
    656             f[i]=ccc[i]%M;
    657         if(op==-1){
    658             long long inv=qpow(lim,M-2);
    659             for(i=0;i<lim;++i)
    660                 f[i]=f[i]*inv%M;
    661         }
    662     }
    663     long long ta[N*4],tb[N*4];
    664     void mult(long long *a,int n,long long *b,int m,long long *c){
    665         int lim=1;
    666         while(lim<n+m)
    667             lim<<=1;
    668         copy(a,a+n,ta);
    669         copy(b,b+m,tb);
    670         for(int i=n;i<lim;++i)
    671             ta[i]=0;
    672         for(int i=m;i<lim;++i)
    673             tb[i]=0;
    674         NTT(ta,lim,1);
    675         NTT(tb,lim,1);
    676         for(int i=0;i<lim;++i)
    677             ta[i]=ta[i]*tb[i]%M;
    678         NTT(ta,lim,-1);
    679         copy(ta,ta+lim,c);
    680     }
    681     long long tmp[N*4],tans[N*4];
    682     void Getinv(long long *a,long long *ans,int lim){
    683         ans[0]=qpow(a[0],M-2);
    684         for(int i=1;i<lim;i<<=1){
    685             for(int j=i;j<(i<<2);++j)
    686                 ans[j]=tans[j]=tmp[j]=0;
    687             for(int j=0;j<(i<<1);++j)
    688                 tmp[j]=a[j];
    689             for(int j=0;j<i;++j)
    690                 tans[j]=ans[j];
    691             NTT(tmp,i<<2,1);
    692             NTT(tans,i<<2,1);
    693             for(int j=0;j<(i<<2);++j)
    694                 tmp[j]=tmp[j]*tans[j]%M*tans[j]%M;
    695             NTT(tmp,i<<2,-1);
    696             for(int j=0;j<(i<<1);++j)
    697                 ans[j]=(2*ans[j]-tmp[j])%M;
    698         }
    699     }
    700     long long tinv[N*4];
    701     void Getln(long long *a,long long *ans,int n){
    702         for(int i=0;i<n-1;++i)
    703             ans[i]=a[i+1]*(i+1)%M;
    704         Getinv(a,tinv,n);
    705         mult(ans,n-1,tinv,n,ans);
    706         for(int i=n;i>=1;--i)
    707             ans[i]=ans[i-1]*inv[i]%M;
    708         ans[0]=0;
    709     }
    710     long long tln[N*4];
    711     void Getexp(long long *a,long long *ans,int n){
    712         ans[0]=1;
    713         for(int i=1;i<n;i<<=1){
    714             for(int j=i;j<(i<<1);++j)
    715                 ans[j]=0;
    716             Getln(ans,tln,i<<1);
    717             for(int j=0;j<(i<<1);++j)
    718                 tln[j]=-tln[j]+a[j];
    719             ++tln[0];
    720             mult(ans,i,tln,i<<1,ans);
    721         }
    722     }
    723     void Getroot(long long *a,long long *ans,int n){
    724         ans[0]=1;
    725         for(int i=1;i<n;i<<=1){
    726             fill(ans+i,ans+(i<<1),0);
    727             Getinv(ans,tinv,i<<1);
    728             mult(tinv,i<<1,a,i<<1,tinv);
    729             for(int j=0;j<(i<<1);++j)
    730                 ans[j]=(ans[j]+tinv[j])*inv[2]%M;
    731         }
    732     }
    733     long long ttln[N*4];
    734     void Getpow(long long *a,long long *ans,int n,int m){
    735         Getln(a,ttln,m);
    736         for(int i=0;i<m;++i)
    737             ttln[i]=ttln[i]*n%M;
    738         Getexp(ttln,ans,m);
    739     }
    740 };
    741 int n,m;
    742 long long f[N*4],g[N*4],h[N*4],hd[N*4],tmp[N*4],eh[N*4],tmp2[N*4],inv[N*4];
    743 void Newton(int lim){
    744     f[0]=f[1]=0;
    745     for(int i=2;i<lim;i<<=1){
    746         poly::Getexp(f,g,i<<1);
    747         for(int j=(i<<1)-1;j>=1;--j)
    748             g[j]=g[j-1];
    749         g[0]=0;
    750         for(int j=0;j<(i<<1);++j)
    751             h[j]=(f[j]+g[j])%M;
    752         poly::Getexp(h,eh,i<<1);
    753         poly::mult(eh,i<<1,h,i<<1,tmp);
    754         ++h[0];
    755         ++g[0];
    756         poly::mult(g,i<<1,h,i<<1,tmp2);
    757         poly::mult(tmp2,i<<1,eh,i<<1,tmp2);
    758         for(int j=(i<<1);j>=1;--j){
    759             tmp2[j]=-tmp2[j-1];
    760             tmp[j]=-tmp[j-1];
    761         }
    762         tmp2[0]=1;
    763         for(int j=0;j<(i<<1);++j)
    764             tmp[j]=(tmp[j]+f[j])%M;
    765         poly::Getinv(tmp2,inv,i<<1);
    766         poly::mult(inv,i<<1,tmp,i<<1,h);
    767         for(int j=0;j<(i<<1);++j)
    768             f[j]=(f[j]-h[j])%M;
    769     }
    770 }
    771 long long rt[N*4],X[N*4],Y[N*4],p1[N*4],p2[N*4],p[N*4],e1[N*4],e2[N*4];
    772 long long fd[N*4],gd[N*4],as[N*4],ans[N*4],as2[N*4];
    773 int lim=1;
    774 int main(){
    775     cin>>n>>M;
    776     int tmpp=M-1;
    777     vector<int> dz;
    778     for(int i=2;i*i<=tmpp;++i)
    779         while(tmpp%i==0){
    780             tmpp/=i;
    781             dz.push_back(i);
    782         }
    783     if(tmpp!=1)
    784         dz.push_back(tmpp);
    785     for(int i=2;i<M;++i){
    786         int z=M-1;
    787         bool fl=true;
    788         for(auto it:dz)
    789             if(poly::qpow(i,z/it)==1){
    790                 fl=false;
    791                 break;
    792             }
    793         if(fl){
    794             poly::g=i;
    795             break;
    796         }
    797     }
    798     poly::init(262144);
    799     ++n;
    800     while(lim<=n*2)
    801         lim<<=1;
    802     Newton(n+1);
    803     memset(inv,0,sizeof(inv));
    804     poly::Getexp(f,g,n+1);
    805     for(int j=n;j>=1;--j)
    806         g[j]=g[j-1];
    807     g[0]=0;
    808     for(int j=0;j<=n;++j)
    809         h[j]=(f[j]+g[j])%M;
    810     poly::Getexp(h,eh,n+1);
    811     for(int j=1;j<=n;++j)
    812         tmp[j]=-eh[j-1];
    813     tmp[0]=1;
    814     poly::Getln(tmp,as2,n+1);
    815     for(int j=1;j<=n;++j)
    816         as2[j]=(as2[j]-f[j])%M;
    817     poly::mult(eh,n+1,h,n+1,X);
    818     for(int i=0;i<=n;++i)
    819         eh[i]=(X[i]+eh[i])%M;
    820     for(int i=n;i>=1;--i){
    821         eh[i]=eh[i-1];
    822         Y[i]=eh[i];
    823     }
    824     eh[0]=0;
    825     poly::mult(eh,n+1,g,n+1,eh);
    826     for(int i=1;i<=n;++i)
    827         h[i]=(-eh[i]-Y[i])%M;
    828     h[0]=1;
    829     poly::Getln(h,as,n+1);
    830     for(int i=0;i<=n;++i)
    831         as[i]=(-as[i]+as2[i])%M;
    832     poly::Getexp(as,ans,n+1);
    833     --n;
    834     for(int i=1;i<=n;++i)
    835         printf("%lld\n",(ans[i]*poly::fac[i]%M+M)%M);
    836 }
    837 ```