PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: harsh_h
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Combinatorics
PROBLEM:
Count the number of boolean arrays A containing a zeros and b ones that satisfy the following condition:
- Construct a new boolean array B by concatenating all the prefixes of A in order.
B should have an equal number of ones at even and odd positions.
EXPLANATION:
Suppose A_i = 1. Let’s see which positions of B it causes to become 1.
The first time is when the i-th prefix is appended to B; meaning index (1+2+\ldots + i) will contain a 1.
Let S_i = (1 + 2 + \ldots + i).
After that, observe that:
- Index (S+i) of B will contain a 1, when the (i+1)-th prefix is appended.
- Index (S+i+(i+1)) will contain a 1, when the (i+2)-th prefix is appended.
- Index (S+i+(i+1)+(i+2)) will contain a 1, when the (i+3)-th prefix is appended.
\vdots
Now, we don’t care about the actual indices: only their parity.
Along with the fact that (a+b) (i.e the length of A) is even, if you analyze what’s going in terms of parity, you’ll notice that:
- If i is odd, it will cause an equal number of odd and even indices in B to contain ones.
- If i is even, the difference between the number of ones at odd and even indices in B will be exactly one.
- In particular, if i \equiv 0 \pmod 4, one extra even index will contain a 1. Otherwise, one extra odd index will contain a 1.
Why?
Suppose i is odd.
Then,
- i is odd, so S+i has a different parity from S.
- i+1 is even, so S+i+(i+1) has the same parity as S+i.
- S+i+(i+1) + (i+2) has a different parity from S+i+(i+1)
\vdots
More generally, the parities follow the pattern 011001100110\ldots where 0 means the same parity as S and 0 means the opposite parity.
Now, since a+b is even, an odd index in A will contribute to an even number of indices in B.
However, from the pattern of parities above, it’s evident that the result is an equal number of even and odd parities (no matter what the initial parity of S is); since breaking the pattern into blocks of 2 gives us a 1 and a 0 in every block.
So, if i is odd, it’ll change the counts of 1 at even and odd parities equally, as claimed.
When i is even, the situation is similar: we’ll have a parity pattern of two zeros followed by two ones over and over, i.e, 001100110011\ldots
The only difference now, is that an odd number of indices in B are affected.
That means, if S is even, there will be exactly one more 1 at an even position than an odd one; and if S is odd, there will be exactly one more 1 at an odd position.
Now, S = 1 + 2 + \ldots + i.
When i is even, S is even if i is a multiple of 4, and odd otherwise (i.e when i has a remainder of 2 when divided by 4).
Since our aim is to make the even and odd index counts of 1 in B equal, what this tells us is that ones placed at odd indices of A don’t really matter.
As for the ones placed at even indices, there should be an equal number at indices that are 0\pmod 4 and 2\pmod 4.
Let N = a+b be the total length of A.
Let x denote the number of indices that are 0\pmod 4 and y be the number that are 2\pmod 4.
Then, to obtain a valid array A, we must distribute an equal number of ones to the x and y positions, and then everything else can be distributed to the other (odd) positions in any way.
In particular, if we fix k to be the number of ones in the x positions,
- There are \binom{x}{k} ways to choose where the ones go.
- An equal number of ones go to the y positions. \binom{y}{k} ways to choose where they go.
- N-x-y odd positions remain, which must contain the remaining b-2k ones. \binom{N-x-y}{b-2k} ways to choose their positions.
Summing up across all k, the answer is simply
This takes \mathcal{O}(b) time to compute by just iterating across all k.
TIME COMPLEXITY:
\mathcal{O}(b) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
long long mult(long long x, long long y,long long m){
__int128 x1 =x;
__int128 y1 =y;
__int128 m1 =m;
__int128 z=x1*y1;
__int128 z1=z%m1;
return (long long)z1;
}
long long powerM(long long a,long long b,long long M){
long long res=1ll;
while(b){
if(b%2ll==1ll){
res=mult(a,res,M);
}
a=mult(a,a,M);b/=2ll;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
cin >> t;
while (t--) {
ll a, b;
cin >> a >> b;
ll n = (a+b);
vector<ll> fact(n+1, 1), inv_fact(n+1, 1);
for (ll i = 1; i <= n; i++) fact[i] = (fact[i-1]*i)%mod;
inv_fact[n] = powerM(fact[n], mod-2, mod);
for (ll i = n-1; i >= 0; i--) inv_fact[i] = (inv_fact[i+1]*(i+1))%mod;
auto C = [&](ll n, ll k)->ll {
if(n>=k && k>=0){
ll ret = fact[n];
ret *= inv_fact[k];
ret %= mod;
ret *= inv_fact[n-k];
ret %= mod;
return ret;
}else{
return 0;
}
};
ll ans = 0;
ll n_4floor = n/4;
ll n_4ceil = n/2-n/4;
for (ll i = 0; i <= b; i += 2) {
ll add = C(n/2, b-i);
add *= C(n_4ceil, i/2);
add %= mod;
add *= C(n_4floor, i/2);
add %= mod;
ans += add;
ans %= mod;
}
cout << ans << '\n';
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define md 1000000007
#define N 2000001
int fac[N];
int modex(int a, int b){
if(b == 0){
return 1;
}
a %= md;
int temp = modex(a, b / 2);
temp *= temp;
temp %= md;
if(b % 2){
temp *= a;
temp %= md;
}
return temp;
}
int mod(int a, int b){
a %= md;
return (a * modex(b, md - 2)) % md;
}
int ncr(int n, int r){
if(n < r){
return 0;
}
if(n < 0 || r < 0){
return 0;
}
return mod(fac[n], fac[r] * fac[n - r]);
}
int32_t main() {
fac[0] = 1;
for(int i = 1; i < N; i++){
fac[i] = fac[i - 1] * i;
fac[i] %= md;
}
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int k = (a + b) / 4;
int l = k;
if((a + b) % 4){
l++;
}
int m = a + b - l - k;
int ans = 0;
for(int i = 0; i <= b / 2; i++){
int temp = ncr(m, b - 2 * i) * ncr(k, i);
temp %= md;
temp *= ncr(l, i);
temp %= md;
ans += temp;
ans %= md;
}
cout<<ans<<"\n";
}
}
Editorialist's code (PyPy3)
mod = 10**9 + 7
fac = [1]
for i in range(1, 3 * 10**6): fac.append(fac[-1] * i % mod)
inv = fac[:]
inv[-1] = pow(inv[-1], mod-2, mod)
for i in reversed(range(1, 3 * 10**6 - 1)): inv[i] = inv[i+1] * (i+1) % mod
def C(n, r):
if n < r or r < 0: return 0
return fac[n] * inv[r] % mod * inv[n-r] % mod
for _ in range(int(input())):
a, b = map(int, input().split())
x, y = len(range(2, a+b+1, 4)), len(range(4, a+b+1, 4))
ans = 0
for i in range(b//2 + 1):
ans += C(x, i) * C(y, i) * C(a+b-x-y, b-2*i) % mod
print(ans % mod)