PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Elementary combinatorics
PROBLEM:
Toofan has an array A, with elements between 0 and K. Each 0 can be replaced by an integer from 1 to K to obtain a candidate passcode.
Toofan will try every possible passcode that matches A. However, there’s no need to try both a passcode and its reverse.
How many passcodes must be tried in the worst case?
EXPLANATION:
Let c denote the number of zeros in A.
Clearly, there are K^c ways of replacing these zeros and obtaining a valid array B that matches A at the non-zero position.
Not all of these need to be counted. In particular, we can classify the arrays we obtain into three classes:
- B matches A, but \text{reverse}(B) doesn’t match A.
Such arrays must be counted once, and are indeed counted only once. - B matches A, \text{reverse}(B) matches A, and B = \text{reverse}(B), i.e. B is a palindrome.
Such arrays must also be counted once, and are counted once currently. - B matches A, \text{reverse}(B) matches A, but B \neq \text{reverse}(B).
Here, only one of B and \text{reverse}(B) needs to be counted, but currently both of them are.
So, our goal is to count arrays of the third type, and subtract them from K^c to get the answer.
That is, we want to count the number of non-palindromic arrays such that the array and its reverse both match A.
This is equivalent to saying that B matches both A and \text{reverse}(A), so let’s see what such arrays look like.
Let R = \text{reverse}(A).
Then,
- If R_i and A_i are both non-zero for some i, but R_i \neq A_i, then no array B matches both A and R.
If this happens then there’s nothing to subtract, the answer is just K^c.
This is case is trivial, so we proceed assuming it isn’t the case. - If either A_i or R_i is non-zero, the value of B_i is fixed to this non-zero value and we have no choice.
- If both A_i and R_i are zero, B_i can technically take any of K choices.
However, we need to ensure that palindromes aren’t counted, and that if B is counted, \text{reverse}(B) is not (since our aim is to subtract exactly one of them, not both).
There are a couple of ways of doing this, here’s one of them.
First, observe that after fixing the elements of B that are constrained by A and R = \text{reverse}(A), B will look something like a palindrome: if B_i is fixed, B_{N+1-i} will also be fixed to the same value.
For convenience, let’s just ignore such palindromic fixed positions, and pretend that B is filled with zeros - this is an equivalent problem since in practice we can just reduce N by the number of filled positions.
Now, we want B to not be a palindrome - so it must have some index i such that B_i \neq B_{N+1-i}.
Let’s fix the leftmost such index i.
Note that i must satisfy 2 i \leq N to be a valid leftmost differing index.
Then,
- For indices j = 1, 2, 3, \ldots, i-1, B_j = B_{N+1-j} must hold, since i is the first differing position.
- There are K^{i-1} ways to choose values for the prefix, which then also fixes the last i-1 elements.
- B_i \neq B_{N+1-i} must hold.
Further, to ensure that we don’t count both B and \text{reverse}(B), we can enforce B_i \lt B_{i+1}.- There are (K-1) + (K-2) + (K-3) + \ldots + 1 = \frac{K\cdot (K-1)}{2} ways to fix the values of B_i and B_{N+1-i} satisfying this.
This is because B_i can be anything from 1 to K, and then B_{N+1-i} has K - B_i choices to be greater than it; so the above expression comes from trying all values of B_i.
- There are (K-1) + (K-2) + (K-3) + \ldots + 1 = \frac{K\cdot (K-1)}{2} ways to fix the values of B_i and B_{N+1-i} satisfying this.
- There are N - 2i positions yet unfilled - they can take any value since we’ve already ensured that B is different from its reverse, and only one of them is being counted.
So, for each i such that 2i \leq N, we want to subtract K^{i-1}\cdot K^{N - 2i}\cdot \frac{K\cdot (K-1)}{2} = \frac{K\cdot (K-1)}{2} \cdot K^{N-1-i} from the answer.
Note that this is after reducing N to the number of zeros in the constrained B.
This is simple enough to do by just iterating through all values of i; and after performing all subtractions, we have our answer.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n,k; cin >> n >> k;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
ll tot = 1, both_ways = 1, pal_ways = 1;
rep1(i,n/2){
ll j = n-i+1;
ll x = (a[i]!=0), y = (a[j]!=0);
if(x+y == 0){
both_ways = both_ways*k%MOD*k%MOD;
pal_ways = pal_ways*k%MOD;
tot = tot*k%MOD*k%MOD;
}
else if(x+y == 1){
tot = tot*k%MOD;
}
else{
if(a[i] != a[j]){
both_ways = pal_ways = 0;
}
}
}
if(n&1){
if(a[ceil2(n,2)] == 0){
tot = tot*k%MOD;
both_ways = both_ways*k%MOD;
pal_ways = pal_ways*k%MOD;
}
}
ll sub = (both_ways-pal_ways+MOD)*((MOD+1)/2)%MOD;
ll ans = (tot-sub+MOD)%MOD;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
mod = 10**9 + 7
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a[::-1]
yes, free = 1, 0
for i in range(n):
if a[i] + b[i] == 0:
free += 1
if a[i] == 0 or b[i] == 0: continue
if a[i] != b[i]: yes = 0
ans = pow(k, a.count(0), mod)
if yes:
pw = 1
ways = (k * (k - 1) // 2) % mod
for i in range(n):
if a[i] > 0 or a[n-1-i] > 0: continue
if i >= n-1-i: break
free -= 2
if free < 0: break
ans -= ways * pw * pow(k, free, mod)
pw = (pw * k) % mod
print(ans % mod)