codeforces-scrape

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

2222.md (15031B)


      1 Source: https://codeforces.com/blog/entry/153275
      2 
      3 We hope you enjoyed these problems!
      4 
      5 [2222A - Замечательный контест](/contest/2222/problem/A)
      6 
      7 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09")
      8 
      9 **Hint 1**
     10 
     11 Consider the case where $k=1$.
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Implementation**
     18 
     19 ```
     20 #include<iostream>
     21 using namespace std;
     22 int t,n;
     23 int main()
     24 {
     25 	cin>>t;
     26 	while(t--)
     27 	{
     28 		cin>>n;
     29 		bool ans=false;
     30 		for(int i=1;i<=n;i++)
     31 		{
     32 			int x;
     33 			cin>>x;
     34 			if(x==100)
     35 			 ans=true;
     36 		}
     37 		if(ans)
     38 		 cout<<"Yes"<<endl;
     39 		else
     40 		 cout<<"No"<<endl;
     41 	}
     42 }
     43 ```
     44 
     45 [2222B - Художественное сбалансированное дерево](/contest/2222/problem/B)
     46 
     47 Author: [lizhous](/profile/lizhous "Эксперт lizhous")
     48 
     49 **Hint 1**
     50 
     51 Consider for a given $p$, which elements can be placed at $p$ with one reversal operation.
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Implementation**
     58 
     59 ```
     60 #include<iostream>
     61 #include<cstdio>
     62 #include<algorithm>
     63 #include<queue>
     64 #define int long long
     65 using namespace std;
     66 int n,a,x,m,sum;
     67 priority_queue <int> nm[2];
     68 bool hv[2];
     69 signed main()
     70 {
     71 	ios::sync_with_stdio(false);
     72 	cin.tie(0);
     73 	cout.tie(0);
     74 	int T;
     75 	cin>>T;
     76 	while(T--)
     77 	{
     78 	    sum=0;
     79 		hv[0]=hv[1]=0;
     80 		while(!nm[0].empty()) nm[0].pop();
     81 		while(!nm[1].empty()) nm[1].pop();
     82 		cin>>n>>m;
     83 		for(int i=1;i<=n;i++)
     84 		{
     85 			cin>>a;
     86 			nm[i&1].push(a);
     87 			sum+=a;
     88 		}
     89 		for(int i=1;i<=m;i++)
     90 		{
     91 			cin>>x;
     92 			if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1])
     93 			{
     94 				sum-=nm[x&1].top();
     95 				nm[x&1].pop();
     96 				hv[x&1]=1;
     97 			}
     98 		}
     99 		cout<<sum<<"\n";
    100 	}
    101 }
    102 ```
    103 
    104 [2222C - Разбиение по медиане](/contest/2222/problem/C)
    105 
    106 Author: [ma2021tyoi0037](/profile/ma2021tyoi0037 "Эксперт ma2021tyoi0037")
    107 
    108 **Hint 1**
    109 
    110 Consider how to determine whether the median of an interval equals $x$.
    111 
    112 **Hint 2**
    113 
    114 What could be the median of each subsequence?
    115 
    116 **Tutorial**
    117 
    118 Tutorial is loading...
    119 
    120 **Implementation**
    121 
    122 ```
    123 #include<iostream>
    124 #include<cstring>
    125 #include<algorithm>
    126 #include<cmath>
    127 using namespace std;
    128 const int N=5e3+10;
    129 int n,a[N],b[N],mid,dp[N];
    130 void run(){
    131     cin>>n;
    132     for(int i=1;i<=n;i++)cin>>a[i];
    133     memcpy(b+1,a+1,n<<2);
    134     sort(b+1,b+n+1);
    135     mid=b[(n+1)>>1];
    136     for(int i=1;i<=n;i++){
    137         if(a[i]==mid){
    138             a[i]=0;
    139             continue;
    140         }
    141         a[i]=(a[i]>mid?1:-1);
    142     }
    143     for(int i=1,flg=0;i<=n;i++){
    144         dp[i]=0;
    145         flg=!a[i];
    146         if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1;
    147         for(int j=i-3,sm=a[i];j>=0;j-=2){
    148             flg+=!a[j+1];
    149             flg+=!a[j+2];
    150             sm+=a[j+1]+a[j+2];
    151             if(abs(sm)>=flg or (j and !dp[j]))continue;
    152             dp[i]=max(dp[i],dp[j]+1);
    153         }
    154         // cout<<dp[i]<<" \n"[i==n];
    155     }
    156     cout<<dp[n]<<'\n';
    157 }
    158 int main(){
    159     cin.tie(0);
    160     cout.tie(0);
    161     ios::sync_with_stdio(0);
    162     int T;
    163     cin>>T;
    164     while(T--)run();
    165 }
    166 ```
    167 
    168 [2222D - Построение перестановки](/contest/2222/problem/D)
    169 
    170 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09")
    171 
    172 **Hint 1**
    173 
    174 Try to perform a prefix sum on $a$.
    175 
    176 **Hint 2**
    177 
    178 Consider what the upper bound of the answer is.
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Implementation**
    185 
    186 ```
    187 #include<iostream>
    188 #include<algorithm>
    189 using namespace std;
    190 #define N 200010
    191 int t,n,a[N],p[N];
    192 pair<long long,int> b[N];
    193 int main()
    194 {
    195 	ios::sync_with_stdio(false);
    196 	cin.tie(0);
    197 	cout.tie(0);
    198 	cin>>t;
    199 	while(t--)
    200 	{
    201 		cin>>n;
    202 		b[0].first=0;
    203 		for(int i=1;i<=n;i++)
    204 		{
    205 			cin>>a[i];
    206 			b[i].first=b[i-1].first+a[i];
    207 			b[i].second=i;
    208 		}
    209 		for(int i=n;i>=1;i--)
    210 		 b[i].first=b[i-1].first;
    211 		sort(b+1,b+n+1);
    212 		for(int i=n;i>=1;i--)
    213 		 p[b[i].second]=n-i+1;
    214 		for(int i=1;i<=n;i++)
    215 		 cout<<p[i]<<" \n"[i==n];
    216 	}
    217 }
    218 ```
    219 
    220 [2222E - Докопаться до правды](/contest/2222/problem/E)
    221 
    222 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09")
    223 
    224 **Hint 1**
    225 
    226 Try to use $0$ and $2^n-1$ in the solution.
    227 
    228 **Tutorial**
    229 
    230 Tutorial is loading...
    231 
    232 **Implementation**
    233 
    234 ```
    235 #include<iostream>
    236 #include<set>
    237 using namespace std;
    238 int t,n;
    239 set<long long> s;
    240 int makeI(long long x)
    241 {
    242 	cout<<"I "<<x<<endl;
    243 	int ans=0;
    244 	cin>>ans;
    245 	return ans;
    246 }
    247 int makeQ(long long y)
    248 {
    249 	cout<<"Q "<<y<<endl;
    250 	int ans=0;
    251 	cin>>ans;
    252 	return ans;
    253 }
    254 int query(long long x)
    255 {
    256 	int res=makeQ(x);
    257 	for(long long w:s)
    258 	if(w>=x)
    259 	 res--;
    260 	return res;
    261 }
    262 long long guess(int n)
    263 {
    264 	long long pre=0;
    265 	for(int i=n-1;i>=0;i--)
    266 	if(query(pre|(1ll<<i))>0)
    267 	{
    268 		pre|=(1ll<<i);
    269 	}
    270 	return pre;
    271 }
    272 int main()
    273 {
    274 	cin>>t;
    275 	while(t--)
    276 	{
    277 		cin>>n;
    278 		s.clear();
    279 		cout<<0<<endl;
    280 		s.insert(0);
    281 		int res1=makeI(0);
    282 		if(res1==1)
    283 		{
    284 			makeI((1ll<<n)-1);
    285 			long long w=guess(n);
    286 			cout<<"A "<<1<<" "<<w<<endl;
    287 			continue;
    288 		}
    289 		long long c=guess(n);
    290 		s.insert(c);
    291 		if(c==(1ll<<n)-1)
    292 		{
    293 			int res2=makeI(1);
    294 			if(res2!=res1)
    295 			{
    296 				cout<<"A "<<3<<" "<<c<<endl;
    297 			}
    298 			else
    299 			{
    300 				cout<<"A "<<2<<" "<<c<<endl;
    301 			}
    302 			continue;
    303 		}
    304 		int res2=makeI((1ll<<n)-1);
    305 		if(query((1ll<<n)-1)>0)
    306 		{
    307 			cout<<"A "<<2<<" "<<c<<endl;
    308 		}
    309 		else
    310 		{
    311 			cout<<"A "<<3<<" "<<c<<endl;
    312 		}
    313 	}
    314 }
    315 ```
    316 
    317 [2222F - Построение дерева](/contest/2222/problem/F)
    318 
    319 Author: [hzy_____](/profile/hzy_____ "Ученик hzy_____") Preparation: [Rebex](/profile/Rebex "Кандидат в мастера Rebex")
    320 
    321 **Hint 1**
    322 
    323 Under what circumstances can an edge with cost $w$ be added between vertex $u$ and vertex $v$ in a new graph?
    324 
    325 **Hint 2**
    326 
    327 Consider divide and conquer.
    328 
    329 **Tutorial**
    330 
    331 Tutorial is loading...
    332 
    333 **Implementation**
    334 
    335 ```
    336 #include <iostream>
    337 #include <algorithm>
    338 #include <cstdio>
    339 #include <vector>
    340 
    341 using namespace std;
    342 
    343 const int S=300005;
    344 
    345 int n,m,k;
    346 vector<pair<int,int> > vec[S];
    347 int fa[S],hei[S],pt[S],fa2[S];
    348 int top,*pot[S*3],val[S*3];
    349 long long ans;
    350 
    351 int fnd(int x){return fa[x]==x?x:fnd(fa[x]);}
    352 int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);}
    353 
    354 inline void push(int &x){pot[++top]=&x,val[top]=x;}
    355 inline void pop(){*pot[top]=val[top],top--;}
    356 
    357 inline void merge(int x,int y,int w)
    358 {
    359     int rx=fnd(x),ry=fnd(y);
    360     if(rx==ry) return;
    361     int px=pt[rx],py=pt[ry];
    362     if(px!=0&&py!=0)
    363     {
    364         int rx=fnd2(px),ry=fnd2(py);
    365         if(rx!=ry) ans+=w,fa2[rx]=fa2[ry];
    366     }
    367     if(hei[rx]>hei[ry]) swap(rx,ry);
    368     push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1);
    369     push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]);
    370     push(fa[rx]),fa[rx]=ry;
    371 }
    372 
    373 void doit(int l,int r,int w)
    374 {
    375     if(l==r) return;
    376     int tp=top;
    377     int mid=l+r>>1;
    378     for(int i=r;i>=mid+1;i--)
    379         for(auto t:vec[i]) merge(t.first,t.second,w);
    380     doit(l,mid,w);
    381     while(top>tp) pop();
    382     for(int i=l;i<=mid;i++)
    383     {
    384         if(!vec[i].empty()&&w==i) w++;
    385         for(auto t:vec[i]) merge(t.first,t.second,w);
    386     }
    387     doit(mid+1,r,w);
    388     while(top>tp) pop();
    389 }
    390 
    391 inline void slove()
    392 {
    393     cin>>n>>m>>k;
    394     for(int i=0;i<=m;i++) vec[i].clear();
    395     for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y);
    396     vector<int> tmp;
    397     for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x);
    398     sort(tmp.begin(),tmp.end());
    399     tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    400     k=tmp.size();
    401     for(int i=1;i<=n;i++) pt[i]=0;
    402     for(int i=0;i<k;i++) pt[tmp[i]]=i+1;
    403     for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;
    404     for(int i=1;i<=k;i++) fa2[i]=i;
    405     ans=0;
    406     doit(0,m,0);
    407     for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void();
    408     cout<<ans<<'\n';
    409 }
    410 
    411 int main()
    412 {
    413     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    414     int T;
    415     cin>>T;
    416     while(T-->0) slove();
    417     return 0;
    418 }
    419 ```
    420 
    421 [2222G - Статистика на дереве](/contest/2222/problem/G)
    422 
    423 Author: [Lyz09](/profile/Lyz09 "Кандидат в мастера Lyz09") Developer: [Z-301](/profile/Z-301 "Легендарный гроссмейстер Z-301")
    424 
    425 **Hint 1**
    426 
    427 What is the value of a path that passes through the centroid of a tree?
    428 
    429 **Hint 2**
    430 
    431 What is the value of a path that does not pass through the centroid of a tree?
    432 
    433 **Hint 3**
    434 
    435 This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct.
    436 
    437 **Tutorial**
    438 
    439 Tutorial is loading...
    440 
    441 **Implementation**
    442 
    443 ```
    444 #include <algorithm>
    445 #include <cstring>
    446 #include <cstdio>
    447 #include <vector>
    448 #include <queue>
    449 using namespace std;
    450 typedef long long ll;
    451 typedef vector<int> vi;
    452 class edge{
    453 	public:
    454 		edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;}
    455 		int v, w, c, nxt;
    456 };
    457 class graph{
    458 	private:
    459 		vector<int> head;vector<edge> e;
    460 	public:
    461 		void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);}
    462 		graph(){}graph(int n){init(n);}
    463 		inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;}
    464 		inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;}
    465 		inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;}
    466 		inline int& h(int u){return head[u];}
    467 		inline edge& operator[](int i){return e[i];}
    468 }G;
    469 const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N];
    470 int t, n, al, mns, rt, sz[N], cnt[N];
    471 void dfs(int u, int fa){int mx = 0;sz[u] = 1;
    472 	for (int i = G.h(u);i != -1;i = G[i].nxt){
    473 		int v = G[i].v;if (v == fa) continue;
    474 		dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);
    475 	}mx = max(mx, al - sz[u]);
    476 	if (mx < mns) rt = u, mns = mx;
    477 }
    478 void dfs1(int u, int fa, int mx, int rt){
    479 	a[rt].push_back(max(mx, sz[u]));
    480 	for (int i = G.h(u);i != -1;i = G[i].nxt){
    481 		int v = G[i].v;if (v == fa) continue;
    482 		dfs1(v, u, max(mx, sz[u] - sz[v]), rt);
    483 	}
    484 }
    485 void calc(vi& a, vector<ll>& s, vi& b, int o){
    486 	int p = upper_bound(a.begin(), a.end(), o) - a.begin();
    487 	for (int i = 0, j;i < b.size();i ++){
    488 		j = upper_bound(a.begin(), a.end(), b[i]) - a.begin();
    489 		if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p);
    490 		if (j < a.size()) ans[o] -= a.size() - j, s[j] ++;
    491 	}
    492 }
    493 void dfs2(int u, int fa){vi vc;
    494 	for (int i = G.h(u);i != -1;i = G[i].nxt){
    495 		int v = G[i].v, w = sz[v];if (v == fa) continue;
    496 		ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w);
    497 	}sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end());
    498 	for (int x : vc) for (int y : vc) if (x < y)
    499 	ans[n - x - y] += 1ll * cnt[x] * cnt[y];
    500 	for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0;
    501 	for (int i = G.h(u);i != -1;i = G[i].nxt){
    502 	int v = G[i].v;if (v != fa) dfs2(v, u);}
    503 }
    504 void solve(int u){vi to;
    505 	for (int i = G.h(u);i != -1;i = G[i].nxt){
    506 		int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v);
    507 		sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0);
    508 	}
    509 	for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]);
    510 	for (int v : to){ll ls = 0;
    511 		for (ll& x : b[v]) ls = x += ls;
    512 		for (int i = 0;i < a[v].size();i ++)
    513 		ans[max(a[v][i], n - sz[v])] ++,
    514 		ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear();
    515 	}dfs2(rt, 0);
    516 }
    517 int main(){scanf("%d", &t);
    518 	while (t --){scanf("%d", &n), G.init(n);
    519 		for (int i = n - 1, u, v;i --;)
    520 		scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3);
    521 		al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n;
    522 		for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n');
    523 	}
    524 }
    525 ```
    526 
    527 [2222H - Сортировка подсчётом?](/contest/2222/problem/H)
    528 
    529 Author: [CutieSmileHaruka](/profile/CutieSmileHaruka "Гроссмейстер CutieSmileHaruka")
    530 
    531 **Hint 1**
    532 
    533 You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(b) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?
    534 
    535 **Hint 2**
    536 
    537 You are given an array $a$. How to count the number of arrays $b$ that satisfy $f(f(b)) = a$ and $ \forall 1 \le i \le n, b_i \le r_i $.?
    538 
    539 **Hint 3**
    540 
    541 How many arrays $a$ satisfy there exists an array $b$ such that $f(f(b)) = a$?
    542 
    543 **Hint 4**
    544 
    545 [The partition numbers](https://oeis.org/A000041).
    546 
    547 **Tutorial**
    548 
    549 Tutorial is loading...
    550 
    551 **Implementation**
    552 
    553 ```
    554 // 全身全霊!MORE MORE JUMP!!
    555 #include <algorithm>
    556 #include <cstring>
    557 #include <cstdio>
    558 #include <vector>
    559 #include <queue>
    560 #define mod 998244353
    561 using namespace std;
    562 typedef __int128_t lll;
    563 template<typename T, const int M>
    564 struct BHasher{inline int operator()(T x){return x % M;}};
    565 template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>
    566 struct HashMap{
    567 	struct node{int nx;T1 ky;T2 vl;};
    568 	int h[M];vector<node> nd;Hsr hsh;
    569 	HashMap(){memset(h, -1, sizeof(h));}
    570 	void clear(){memset(h, -1, sizeof(h)), nd.clear();}
    571 	inline bool find(T1 k){int p = hsh(k);
    572 		for (int i = h[p];i != -1;i = nd[i].nx)
    573 		if (nd[i].ky == k) return 1;return 0;
    574 	}
    575 	inline T2& operator[](T1 k){int p = hsh(k);
    576 		for (int i = h[p];i != -1;i = nd[i].nx)
    577 		if (nd[i].ky == k) return nd[i].vl;
    578 		nd.push_back((node){h[p], k, T2()});
    579 		return nd[h[p] = nd.size() - 1].vl;
    580 	}
    581 };
    582 const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id;
    583 int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt;
    584 unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M];
    585 void dfs(int p, int sm){
    586 	if (p > n){m ++;
    587 		memcpy(ps[m], sk, sizeof(sk));
    588 		memcpy(b[m], bb, sizeof(bb));
    589 		return;
    590 	}
    591 	for (int x = 0;x <= n && sm <= n;x ++, sm += p){
    592 		if (x) sk[++ c] = p;
    593 		bb[p] = x, dfs(p + 1, sm);
    594 		if (x) sk[c --] = 0;
    595 	}
    596 }
    597 inline lll hsh(unsigned char* A){lll st = 0;
    598 	for (int i = 1;i <= n;i ++)
    599 	st <<= 1, st |= 1, st <<= A[i];return st;
    600 }
    601 inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;}
    602 inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
    603 int main(){scanf("%d", &t), n = N - 5;
    604 	for (int i = 0;i <= n;i ++){C[i][0] = 1;
    605 	for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}
    606 	while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0);
    607 		memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2);
    608 		for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
    609 		for (int i = 1;i <= m;i ++){
    610 			lll st = hsh(b[i]);id[st] = i;
    611 			for (int j = n, p = -1;j >= 1;j --){
    612 				p += b[i][j] + 1;if (b[i][j])
    613 				to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)];
    614 			}
    615 		}
    616 		for (int i = 1;i <= m;i ++){
    617 			memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0;
    618 			for (int j = 1;j <= n;j ++)
    619 			tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j];
    620 			if (sm[i] == 1) rt = i;
    621 			fa[i] = id[hsh(tmp)];
    622 		}f[1] = dep[1] = dep[rt] = 1;
    623 		for (int i = n, ss = 0;i >= 1;i --){
    624 			for (int o = 1;o <= n;o ++) ss += a[o] == i;
    625 			for (int j = m;j >= 1;j --)
    626 			if (ct[j] <= n - i + 1 && sm[j] <= ss)
    627 			for (int k = 1, x, now;ps[j][k];k ++)
    628 			if (now = f[to[j][x = ps[j][k]]])
    629 			f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod;
    630 		}
    631 		for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]);
    632 		for (int i = 1;i <= n;i ++) cnt += a[i] > 0;
    633 		add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0));
    634 		for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n');
    635 	}
    636 }
    637 ```