TASUMOBC - Editorial

combinatorics
digit-dp
editorial
hard
ltime19

#1

PROBLEM LINK:

Practice
Contest

Author: Tuan Anh
Tester: Gedi Zheng
Editorialist: Praveen Vaka and Praveen Dhinwa

DIFFICULTY:

Medium - Hard

PREREQUISITES:

digit dp, Lucas theorem, combination formula.

PROBLEM:

Our aim is to find S(n) = sum C(n,k) mod 3 for all 0<=k<=n i.e., the sum of all entries in the nth row of modulo 3 pascal triangle.
We just need to output this value modulo 10^9+7

QUICK EXPLANATION:

You can use digit dynamic programming to solve the problem too. Using digit dp and information of lucas theorem, you can
maintain current combination C(n, k) modulo 3 as an extra state parameter.

Any number modulo 3 has to be one of {0, 1, 2}. Use Lucas’ Theorem to figure out the values of C(n, k) mod 3

EXPLANATION:

Notes and definitions
n is not a variable anywhere in this editorial it denotes the input value.
k is a variable which can take values between 0 and n inclusive.
S(n) is just the sum of the binomial coefficients modulo 3
but the value to be outputted is S(n) mod 10^9 + 7.
Note that C(n, k) is defined to be 0 when k > n.
Whenever we write a = b mod n we are denoting the congruence relation

Lucas’ theorem
In number theory, Lucas’s theorem expresses the remainder of division of the binomial coefficient C(n, r) by a
prime number p in terms of the base p expansions of the integers n and r.

Let base p representation of n be n = nk pk + nk-1 pk-1

  • . . + n1 p + n0.
    Let base p representation of r be r = rk pk + rk-1 pk-1
  • . . + r1 p + r0.

Then C(n, r) % p = (C(nk, rk) % p) * . * . (C(n1, r1) % p) * (C(n0, r0) % p)

Digit Dynamic Programming Solution

You can visit the following link to learn digit dp. You can also see one of the editorials written by
me on the topic.

In this problem, we want to count number of numbers k from 0 to n having value of C(n, k) modulo 3, equal to some digit (0, 1 or 2).

Let me describe you a method to find out number of numbers k from 0 to n having value of C(n, k) modulo 3, equal to some digit, let us call
that digit needed. We can solve the problems of counting numbers from 0 to n having some property using digit dp.

Conceptually you can view digit dp as construction/ generation of numbers from most significant digit to least significant digit.
The main idea is that you don’t need to store/ remember the entire constructed number, instead you can only work by simply knowing a few
properties about the constructed number. eg. In our current problem, we don’t need to know the entire digits generated up to now.
Instead we need to store few useful information which is described below.

For applying Lucas’ theorem, we need to write the numbers in ternary representation.
Only thing that we need to store additionally in our dp state would be product of (C(n0, r0) % p) * . * .
(C(ni - 1, ri - 1) % p).

Whenever in the editorial we talk about first id digits, by that we mean the most significant first id digits.

Let dp[id][tight][val][needed] denote the number of numbers whose first id digit have been considered and tight denotes
whether the currently constructed number is equal or less than number formed by first id digits of n.

If tight is true, then it means that currently constructed number is equal to number constructed by first id digits in
ternary representation of N.

If tight is false, then it means that currently constructed number is less than number constructed by first id digits
in ternary representation of N.

val denotes the product of (C(nj, rj) % p) modulo 3 for all j from 0 to id - 1.

needed denotes what types of number we want to count. So we want to count number of numbers k from 0 to n having value of C(n, k) modulo
equal to needed.

Base Case
If id = number of digits in ternary representation of N, then we will check whether the val is equal to needed or not.
If val is equal to needed, then it means that this constructed number is valid. So we will add it to answer.

Transitions
We can consider following options for filling id th digit when we have already filled the first id - 1 digits.

If tight is true, then it means that our constructed number is still equal to number formed by first i digits of N.
Then we can try our current possible digit value from 0 to (id) th digit of N. If we try the digit more than id th digit,
then the constructed number will become greater than number formed by first id digits of N, which will violate the property that
our constructed number should be <= N.

After filling out this state, we will go to id + 1, hence new_i = id + 1.

If we take our current digit id to be strictly less than dig*, then our new_tight will be false.

If we try out current digit x then new_val will be (val * C(i th digit of N, x)) % 3.

If tight is false, then it means that number constructed from first id - 1 digits has become less than number constructed from the
first id - 1 digit of N, So it means that our number can never exceed N, so we can chose the any digit from 0 to 3 and do the transitions
in the same way as explained in the previous paragraph.

Pseudo Code

List bits; 
// Let bits store the ternary representation of n from MSB to LSB (
// ie. most significant bit to least significant bit.

long dp(int id, int tight, int val, int needed) {
	if (memo[id][tight][val] != -1) { // used for memoization.
		return memo[id][tight][val];
	}
	long res = 0;
	if (id == bits.size()) {
		if (val == needed) {  
			// if C(n, r) modulo 3 is equal to desired value,
			// then it means the current generated number is valid and should be counted.
			res = 1;
		}
	} else {
		// tight denotes whether the number generated up to now is exactly equal to first id digits of r or not.
		if (tight > 0) {
			for (int i = 0; i < bits.get(id); i++) {
				res += dp(id + 1, 0, (val * C(bits.get(id), i)) % 3, needed);
			}
			res += dp(id + 1, 1, (val * C(bits.get(id), bits.get(id))) % 3, needed);
		} else {
			for (int i = 0; i < 3; i++) {
				res += dp(id + 1, 0, (val * C(bits.get(id), i)) % 3, needed);
			}
		}
	}
	// memoization
	memo[id][tight][val] = res;
	return res;
}

long ans = (dp(0, 1, 1, 1) + dp(0, 1, 1, 2) * 2) % mod;

Time Complexity
Number of states = Max value of id * max value of tight * max value of val = log(N) * 2 * 3.
Number of transitions = We are trying at most 3 numbers ie. 0, 1, or 2 for our current digit of k.
So overall time complexity will be around 18 log(N).

Another Solution

Input: a number n 
Output: a number S(n) % 10^9+7
getSum(n):
	n3 = getBase3(n)
	(x, y) = getOnesAndTwos(n3)
	return (x + 2 * y) % 109+7
	
Input: a number n
Output: a list of numbers each number is one among {0,1,2} and the list when read from left to right will be will be the base 3 representation of n
getBase3(n):
	return the base 3 representation of n
	
Input: List L representing some number say n in ternary
Output: a pair (x,y) where x is the number of of ones in nth row of the pascal triangle modulo 3 and y the number of twos in the same row
getOnesAndTwos(L):
	if L is empty:
		return (1, 0)
	//The below base is not needed if we have the above one but added for clarity purpose
	if L has only one element d:
		if d is 0 return (1, 0)
		if d is 1 return (2, 0)
		if d is 2 return (2, 1)
	Let d be the first element of L
Let  L’ the list that we get by removing the first element from L
(x’, y’) = getOnesAndTwos(L’)  
if d is 0 return (x’, y’)
if d is 1 return (2*x’, 2*y’)
if d is 2 return (2*x’+y’, x’+2*y’)

Explanation
C(n,k) mod 3 can only be one of the values 0, 1 and 2.
Let ans1 be the number of k’s for which C(n,k) = 1 mod 3
Let ans2 be the number of k’s for which C(n,k) = 2 mod 3
We will have S(n) = ans1 + 2 * ans2

Let us have a look at pascal triangle modulo 3.

0 - 1
1 - 1 1
2 - 1 2 1
3 - 1 0 0 1
4 - 1 1 0 1 1
5 - 1 2 1 1 2 1
6 - 1 0 0 2 0 0 1
7 - 1 1 0 2 2 0 1 1
8 - 1 2 1 2 1 2 1 2 1
9 - 1 0 0 0 0 0 0 0 0 1

For n = 8 we have ans1 = 5 and ans2 = 4 and hence S(8) = 5 * 1 + 4 * 2 = 13

We will use Lucas’ Theorem to find out the values of x and y for a given n.

For a fixed n and an arbitrary k let the ternary representation of n be ar ar-1… a1 a0
with no leading zeroes.
Let the ternary representation of k be br br-1… b1 b0 with leading zeroes
if needed to match up the length of ternary representation of n.
Note that r is fixed for a given n.

We have C(n, k) = C(ar, br) * C(ar-1, br-1) * … * C(a1, b) *
C(a0, b0) mod 3

We have C(n,k) = 0 mod 3 iff there exists at least one i such that C(ai, bi) = 0 the inequality
ai < bi will hold for that i.
We are interested in the k’s which result in a non zero value of C(n, k) mod 3 This will happen only when ai >= bi
for all i.

We can find the values of ans1 and ans2 by writing down a simple recursion.

Some notation first
Let f(x, l) denote suffix of length l+1 of the ternary representation of x

Under this notation we can rewrite the C(n, k) mod 3 as follows
C(n, k) = C(f(n, r), f(k, r)) % 3 = (C(ar, br) * C(f(n, r-1), f(k, r-1)) mod 3

To illustrate by an example
C(2101223, 1101213) = C(2, 1) * C(1, 1) * C(0, 0) * C(1, 1) * C(2, 2) * C(2, 1) mod 3
C(101223, 101213) = C(1, 1) * C(0, 0) * C(1, 1) * C(2, 2) * C(2, 1) mod 3
C(2101223, 1101213) = C(2, 1) * C(101223, 101213) mod 3

Let ans1(L) denote the number of entries with value 1 in f(n, L)th row of the pascal triangle modulo 3 and ans2(L)
denote the number of entries with value 2 in the same row.

f(n,L) is aLaL - 1…a1a0

For computing ans1(L) We are interested number of possible bLbL - 1…b1b0 such that
C(aLaL - 1…a1a0 , bLbL - 1…b1b0)
= 1 mod 3

For computing ans2(L) We are interested number of possible bLbL - 1…b1b0 such that
C(aLaL - 1…a1a0 , bLbL - 1…b1b0) = 2 mod 3

If aL is 0 we have to force the corresponding bL to be 0 otherwise C(aL, bL) would be 0.
So in this case we have ans1(L) = ans1(L-1) and ans2(L) = ans2(L-1) as there is only one way of choosing bL and that results in
C(aL, bL) to be 1.

If aL is 1 we have two possible values for corresponding bL 0 and 1.
So we have ans1(L) = ans1(L-1) * 2 and ans2(L) = ans2(L-1) * 2 as there are two ways of choosing bL and in both C(aL, bL)
will be 1.

If aL is 2 we have three possible values for corresponding bL 0, 1 and 2.
So we have ans1(L) = ans1(L-1)*2 + ans2(L-1)
for bL = 0,2 we have C(aL, bL) = 1
for bL = 1 we desire C(aL, bL) * C(aL - 1…a1a0 ,
bL - 1…b1b0) = 1 mod 3 and hence we need
C(aL - 1…a1a0 ,
bL - 1…b1b0) =
2 mod 3 since C(aL, bL) = 2

Similarly we have ans2(L) = ans1(L-1) + ans2(L-1)*2

We have S(n) = ans1® + 2 * ans2® where r is the the length of ternary representation of n.

One More Solution

Problems to Practice

Please add more problems for practice !!

AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:

setter
tester
editorialist


#2

Very nice problem :wink:


#3

Good problem, loved solving it :slight_smile:

p.s my approach was exactly the last one. Great explanation of each solution (y)


#4

This problem can be easily solved using oeis.org!


#5

How about this approach?

for any n > 5 whenever we have more than 3 numbers in numerator then ans is always going to be
zero (Any 3 continuous numbers such that x * (x + 1) * (x + 2) are always divisible by 3)
Then we only have to calculate for those nCr values where on numerator only 1 or 2 numbers

There may be something wrong with this approach! just wanted to share!


#6

No it is not so always, try for n=8…


#7

yes indeed :slight_smile:


#8

@dpraveen why are we not calculating dp(0,1,1,0) ?? because we need 0 digit also ,and why there is 2*dp(0,1,1,2) ??
got it sorry my mistake in understanding :’(


#9

@adijimmy: Because what we need is the sum of (C(n, k) % 3) for k = 0 to n.
In our case, Let ans_needed denotes number of k’s having (C(n, k) % 3 = needed). So our desired answer will be 0 * ans_0 + 1 * ans_1 + 2 * ans_2.
So it will ans_1 + 2 * ans_2. This is the precise reason for multiplying dp(0,1,1, 2) by 2.


#10

Really - http://oeis.org/A051638 :frowning: (I didn’t try during the contest)


#11

hey @betlista can u help me why my code is giving WA with the 3rd sub-task, though am following he digit dp formulation along with lucas theorem , below is the link to my solution
http://www.codechef.com/viewsolution/5663087


#12

Hey @lord_f

Can you explain how to use this…?

It looks interesting…!!


#13

You simply generate few elements from sequence (found by brute force for example) and enter those in “search” field separated by commas (','), for example: 1, 2, 4, 2, 4, 8, 4, 8, 13, 2, 4, 8, 4, 8, 16, 8, 16, 26, 4, 8, 13, 8, 16, 26


#14

@dpraveen thanks for such a great editorial :slight_smile:


#15

@adijimmy: welcome :slight_smile:


#16

"Let ans1(L) denote the number of entries with value 1 in f(n, L)th row of the pascal triangle modulo 3 and ans2(L) denote the number of entries with value 2 in the same row.

f(n,L) is aLaL - 1…a1a0 "

what does f(n,L)th row refer to here? f(n,L) was defined as the suffix of length l+1 of the base 3 representation of N.


#17

@ironmandhruv f(N, L) is value of aLaL - 1…a1a0.


#18

what you do after getting the sequense