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;
}

6 days ago | [YT] | 2