Abhishek

H.Subtree XOR Counting

In C ++



#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;


ll modpow(ll a, ll e)
{
ll r = 1;
a %= MOD;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}

int main()
{


int t;
cin >> t;

vector<ll> powK, powD, powB, powE, f_prev, f_curr;
vector<int> parent, freq, c;
vector<vector<int>> adj, children;
vector<ll> D_list, D_rev;

while (t--)
{
int N;
ll M;
cin >> N >> M;
ll K = (M + 1) % MOD;


adj.assign(N+1,{});
for(int i=0;i<N-1;i++)
{
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}


parent.assign(N+1,0);
children.assign(N+1,{});
queue<int> q;
parent[1] = -1;
q.push(1);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int v: adj[u])
{
if(parent[v]==0)
{
parent[v] = u;
children[u].push_back(v);
q.push(v);
}
}
}


freq.assign(N+1,0);
c.assign(N+1,0);
int internalCount = 0;
for(int u=1;u<=N;u++){
if(!children[u].empty()){
internalCount++;
int cntLeaf = 0;
for(int v: children[u])
if(children[v].empty()) cntLeaf++;
c[u] = cntLeaf;
freq[cntLeaf]++;
}
}


if(internalCount==0)
{

cout << 0 << "\n";
continue;
}


powK.assign(N+1,0);
powK[0] = 1;
for(int i=1;i<=N;i++)
powK[i] = powK[i-1] * K % MOD;


int maxd = 0;
for(int leafCnt=0; leafCnt<=N; leafCnt++)
if(freq[leafCnt]>0)
maxd = max(maxd, leafCnt+1);


D_list.clear();
{
ll D = M;
while (true) {
D_list.push_back(D);
if (D==0) break;
int b = 64 - __builtin_clzll(D);
D -= (1LL << (b-1));
}
}
D_rev = D_list;
reverse(D_rev.begin(), D_rev.end());


f_prev.assign(maxd+1,1);

ll inv2 = (MOD+1)/2;

for(size_t idx=1; idx<D_rev.size(); idx++){
ll D = D_rev[idx];


powD.assign(maxd+1,0);
powD[0]=1;
ll D1 = (D+1)%MOD;
for(int i=1;i<=maxd;i++)
powD[i] = powD[i-1]*D1 % MOD;

int b = 64 - __builtin_clzll(D);
ll A_int = 1LL<<(b-1);
ll A = A_int % MOD, invA = modpow(A, MOD-2);
ll B_int = (D+1) - A_int, B = (B_int%MOD+MOD)%MOD;
ll E_int = (1LL<<b) - (D+1), E = (E_int%MOD+MOD)%MOD;


powB.assign(maxd+1,0);
powE.assign(maxd+1,0);
powB[0]=powE[0]=1;
for(int i=1;i<=maxd;i++){
powB[i] = powB[i-1]*B % MOD;
powE[i] = powE[i-1]*E % MOD;
}


f_curr.assign(maxd+1,0);
f_curr[0]=1;
for(int d=1; d<=maxd; d++){

ll sum_even = (powD[d] + powE[d]) % MOD * inv2 % MOD;
if((d&1)==0){
ll s1 = (sum_even - powB[d] + MOD)%MOD * invA % MOD;
f_curr[d] = (s1 + f_prev[d]) % MOD;
} else {
f_curr[d] = sum_even * invA % MOD;
}
}
f_prev.swap(f_curr);
}


ll full = powK[N], ans = 0;
for(int leafCnt=0; leafCnt<=N; leafCnt++){
int cnt = freq[leafCnt];
if(!cnt) continue;
int d = leafCnt+1;
ll Qi = f_prev[d];

ll term = (full - powK[N-d]*Qi % MOD + MOD)%MOD;
ans = (ans + term*cnt) % MOD;
}

cout << ans << "\n";
}
return 0;
}

3 days ago | [YT] | 1

Abhishek

G.Adject Or

In C++ language

#include <bits/stdc++.h>
using namespace std;

int main()
{

int T;
cin >> T;
while (T--)
{

int N;
cin >> N;
vector<int> A(N+2), B(N+2);
long long sumA = 0, sumB = 0;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
sumA += A[i];
}
for (int i = 1; i <= N; i++)
{
cin >> B[i];
sumB += B[i];
}

bool ok = true;


if (A[1] != B[1] || A[N] != B[N])
{
ok = false;
}


if (ok && sumB > 0 && sumA == 0)
{
ok = false;
}


if (ok)
{
for (int i = 2; i <= N-1; i++)
{
if (B[i] == 0 && A[i] == 1)
{
if (!(A[i-1] == 0 && A[i+1] == 0))
{
ok = false;
break;
}
}
}
}


if (ok)
{
int i = 1;
while (i <= N)
{
if (B[i] == 1)
{
int l = i;
while (i+1 <= N && B[i+1] == 1)
{
i++;
}
int r = i;
bool hasSeed = false;
for (int j = l; j <= r; j++)
{
if (A[j] == 1)
{
hasSeed = true;
break;
}
}
if (!hasSeed)
{
ok = false;
break;
}
}
i++;
}
}

cout << (ok ? "Yes\n" : "No\n");
}

return 0;
}

3 days ago | [YT] | 1

Abhishek

F.Second mex

In C++ language

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 998244353;


int64 modexp(int64 a, int64 e = MOD - 2)
{
int64 r = 1;
while (e)
{
if (e & 1) r = (r * a) % MOD;
a = (a * a) % MOD;
e >>= 1;
}
return r;
}

int main()
{



static vector<int64> pow2;
int maxN = 200000 + 5;
pow2.resize(maxN);
pow2[0] = 1;
for (int i = 1; i < maxN; i++)
{
pow2[i] = (pow2[i-1] << 1) % MOD;
}

int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++)
{
cin >> A[i];
}

int M = N + 2;
vector<int> freq(M, 0);
for (int x : A) {
if (x < M) freq[x]++;
}

vector<int64> pow2_c(M), w(M), invw(M);
for (int v = 0; v < M; v++)
{
pow2_c[v] = pow2[freq[v]];
if (freq[v] > 0)
{
w[v] = (pow2_c[v] + MOD - 1) % MOD;
invw[v] = modexp(w[v]);
} else {
w[v] = 0;
invw[v] = 0;
}
}

vector<int64> P(M+1, 1), P2(M+1, 1), S(M+1, 0), Z(M+1, 0);
for (int k = 1; k <= M; k++)
{
P[k] = (P[k-1] * w[k-1]) % MOD;
P2[k] = (P2[k-1] * (w[k-1] ? w[k-1] : 1)) % MOD;
Z[k] = Z[k-1] + (freq[k-1] == 0);
S[k] = S[k-1] + (w[k-1] ? invw[k-1] : 0);
if (S[k] >= MOD) S[k] -= MOD;
}

vector<int64> Tprod(M+2, 1);
for (int i = M - 1; i >= 0; i--) {
Tprod[i] = (Tprod[i+1] * pow2_c[i]) % MOD;
}

int64 answer = 0;

for (int k = 1; k <= M+1; k++)
{

if (Z[k] >= 2) continue;
int64 Ck = 0;
int64 Q = (k+1 <= M ? Tprod[k+1] : 1);
if (Z[k] == 1) {

Ck = (P2[k] * Q) % MOD;
}
else
{

Ck = P[k];
Ck = (Ck * S[k]) % MOD;
Ck = (Ck * Q) % MOD;
}
answer = (answer + (int64)k * Ck) % MOD;
}

answer = (answer + MOD - 1) % MOD;

cout << answer << "\n";
}

return 0;
}

3 days ago (edited) | [YT] | 1

Abhishek

E.Double or Append


#include <stdio.h>
#include <stdint.h>

int main(){
int T;
if(scanf("%d",&T)!=1) return 0;
while(T--){
int M;
scanf("%d",&M);
unsigned long long inv = 0;
unsigned long long S = 1; // length of A
unsigned long long P = 0; // sum f[v]*pref[v]
int mex = 1;

for(int i = 0; i < M; i++){
int t;
scanf("%d",&t);
if(t == 1){
// prepend mex
inv += S;
P += S;
S += 1;
mex += 1;
} else {
// double
inv = inv * 2 + P;
P = P * 4;
S = S * 2;
}
printf("%llu", inv);
if(i+1 < M) putchar(' ');
}
putchar('\n');
}
return 0;
}

3 days ago | [YT] | 1

Abhishek

D.Front or Back

#include <stdio.h>
#include <stdint.h>

#define MOD 998244353

// Maximum N per test is up to 2e5 over all tests;
// we just need freq[0..N-1] per test.
static int freq[200000 + 5];

int main(){
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
int N;
scanf("%d", &N);

// Zero out freq[0..N-1]
for (int i = 0; i < N; i++) {
freq[i] = 0;
}

// Read A_i and build frequencies
for (int i = 0, a; i < N; i++) {
scanf("%d", &a);
if (0 <= a && a < N) {
freq[a]++;
}
}

int64_t ans = 1;
int ok = 1;
int half = N / 2;

// For each mirrored pair (k, N-1-k), we need exactly two people
// whose A is either k or N-1-k, and we get 2! = 2 ways to assign them.
for (int k = 0; k < half; k++) {
int k2 = N - 1 - k;
if (freq[k] + freq[k2] != 2) {
ok = 0;
break;
}
ans = (ans * 2) % MOD;
}

// If N is odd, the middle position m = (N-1)/2 must be filled by exactly one person reporting A=m.
if (ok && (N & 1)) {
int m = half; // when N is odd, half == (N-1)/2
if (freq[m] != 1) {
ok = 0;
}
}

if (ok) {
printf("%lld\n", ans);
} else {
printf("0\n");
}
}
return 0;
}

3 days ago | [YT] | 2

Abhishek

C.One Down

#include <stdio.h>
#include <string.h>

int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
int N;
char S[55], Tgt[55];
scanf("%d", &N);
scanf("%s", S);
scanf("%s", Tgt);

int onesS = 0, onesT = 0;
for (int i = 0; i < N; i++) {
if (S[i] == '1') onesS++;
if (Tgt[i] == '1') onesT++;
}

// If target has a '1' where S has '0', impossible.
int ok = 1;
for (int i = 0; i < N; i++) {
if (Tgt[i] == '1' && S[i] == '0') {
ok = 0;
break;
}
}

// We can only remove ones in pairs. Let r = onesS - onesT: must be ≥0 and even.
if (onesS < onesT) ok = 0;
if ((onesS - onesT) % 2 != 0) ok = 0;

printf("%s\n", ok ? "YES" : "NO");
}
return 0;
}

3 days ago | [YT] | 1

Abhishek

B.Sum to 0

#include <stdio.h>

int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
int N;
scanf("%d", &N);

// Impossible for N = 1
if (N == 1) {
printf("-1\n");
continue;
}

// If N is even: just output N/2 of +1 and N/2 of -1
if (N % 2 == 0) {
for (int i = 0; i < N / 2; i++) {
printf("1 ");
printf("-1 ");
}
printf("\n");
}
else {
// N is odd and >= 3
// Use one triple [1, 2, -3] (sum = 0), then fill the rest (even count) with pairs [1, -1]
printf("1 2 -3 ");
int rem = N - 3;
for (int i = 0; i < rem / 2; i++) {
printf("1 ");
printf("-1 ");
}
printf("\n");
}
}
return 0;
}

3 days ago | [YT] | 1

Abhishek

A ..Multiple of 3


#include <stdio.h>
#include <stdlib.h>

int main() {
long long N;
if (scanf("%lld", &N) != 1) return 0;

long long r = N % 3;
long long ans = N;

if (r == 1) {
// e.g. N=4 → 4%3=1 → nearest is 4−1=3
ans = N - 1;
} else if (r == 2) {
// e.g. N=5 → 5%3=2 → nearest is 5+1=6
ans = N + 1;
}

printf("%lld\n", ans);
return 0;
}

3 days ago | [YT] | 2

Abhishek

D.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

//--- Precompute the first ~440k primes by sieving up to 7e6 ---
const int SIEVE_MAX = 7'000'000;
vector<bool> is_prime(SIEVE_MAX+1, true);
is_prime[0] = is_prime[1] = false;
for(int i = 2; i*i <= SIEVE_MAX; i++){
if(is_prime[i]){
for(int j = i*i; j <= SIEVE_MAX; j += i)
is_prime[j] = false;
}
}
// collect primes and build their prefix sums P_k = sum of first k primes
vector<ll> P;
P.reserve(450000);
ll running = 0;
for(int i = 2; i <= SIEVE_MAX; i++){
if(is_prime[i]){
running += i;
P.push_back(running);
if((int)P.size() >= 440000)
break;
}
}
// P[k-1] = sum of first k primes

int t;
cin >> t;
while(t--){
int n;
cin >> n;

vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}

// sort descending and build prefix sums S_k
sort(a.begin(), a.end(), greater<>());
vector<ll> S(n+1, 0);
for(int i = 0; i < n; i++){
S[i+1] = S[i] + a[i];
}

// find largest k in [0..n] with S[k] >= P[k-1]
// (for k=0, P[-1] interpreted as 0)
int best_k = 0;
for(int k = 1; k <= n; k++){
if(k > (int)P.size()) break; // no more primes precomputed
if(S[k] >= P[k-1])
best_k = k;
else
break;
}

// We must remove (n - best_k) to leave best_k “beautiful” elements
cout << (n - best_k) << "\n";
}

return 0;
}

5 days ago | [YT] | 0

Abhishek

C.. Card Game

In C++ language


#include <bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while(T--){
int n;
string s;
cin >> n >> s;
vector<int> A, B;
A.reserve(n);
B.reserve(n);
for(int i = 0; i < n; i++){
if(s[i] == 'A') A.push_back(i+1);
else B.push_back(i+1);
}

bool alice_wins = false;
for(int a: A){
bool bob_can_beat = false;
if(a == 1){
// Bob can beat 1 only by playing some b in [2..n-1]
for(int b: B){
if(2 <= b && b <= n-1){
bob_can_beat = true;
break;
}
}
}
else if(a == n){
// Bob can beat n only by playing b == 1
for(int b: B){
if(b == 1){
bob_can_beat = true;
break;
}
}
}
else {
// For 2 <= a <= n-1: Bob beats a if he has any b > a
for(int b: B){
if(b > a){
bob_can_beat = true;
break;
}
}
}

if(!bob_can_beat){
// Alice has a card 'a' that Bob cannot beat
alice_wins = true;
break;
}
}

cout << (alice_wins ? "Alice\n" : "Bob\n");
}

return 0;
}

5 days ago | [YT] | 2