ANGGRA - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Rami

Tester: Roman Bilyi

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Combinatorics, Maths, Observation.

PROBLEM:

Given three integers N, M and K, Find the number of arrays A of length N such that the prefix sum array S of array A contains at least K elements divisible by M.

EXPLANATION

Let us solve a simpler problem first.

Given N, M and K, find the number of arrays of length N having each value in range [0, M-1] such that exactly K values are 0.

Here, we want K values to be zero and the remaining N-K values to be non-zero. For each non-zero value, we have exactly M-1 choices for that number. So we can select the non-zero values in (M-1)^{N-K} ways.

But till now, we have only chosen the elements in order. They can appear at any of the N-K positions among total N positions.

Assume N = 4, K = 2 and chosen non-zero values be [1, 2] in this order only. Then, there are six following ways to place them among array of size N.

0 0 1 2
0 1 0 2
0 1 2 0
1 0 0 2
1 0 2 0
1 2 0 0

It is easy to see, that it is equivalent to Choosing (N-K) positions out of N positions and for each set of positions, choosing (N-K) non-zero values, which can be done in (M-1)^{N-K} ways, resulting in total ^{N}C_{N-K}*(M-1)^{N-K} ways to select array with exactly K zeroes.

Coming back to original problem, let us Consider prefix sum array modulo M, since We only care about values in prefix sum array modulo M, and (a+b)\%M = (a\%M+b\%M)\%M .

Let’s call this modulo prefix sum array T. It can be seen, that all values in this array are in range [0, M-1].

Let’s assume T_i = x where 0 \leq x < M. Now, what values can T_{i+1} take? We can see, that T_{i+1} can be (x+y)\%M where y can take any value from 0 to M-1. It is easy to see that for each value of y, (x+y) takes a different value, and y takes M distinct values, so T_{i+1} can take all distinct values irrespective of T_{i}.

Hence, we can consider all possible arrays T such that each value is within range [0, M-1] and find a unique array A whose modulo prefix sum array is T. So, there is one-to-one mapping between array A and array T. So, the number of valid ways to choose A array is same as the number of valid ways to choose T array.

Hence, the original problem turns into choosing array T of length N such that each value is independent of each other and at least K values are 0 (Since only 0 in range [0, M-1] is divisible by M). We can individually fix number of 0 to p for K \leq p \leq N and count the number of arrays T with exactly p zeroes.

For computing binomial coefficients, it is better to compute factorials and their inverses in advance, and ^nC_r = \displaystyle\frac{n!}{r!(n-r)!} Details can be found here.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll  long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sc second
#define fr first

using namespace std;

const int mod = 1e9+7;
const int N = 1e5+10;
int n,m,k;
ll fac[N];
ll inv[N];

ll pw(ll x, ll p){
	if(!p)
	    return 1;
	ll z = pw(x,p/2);
	z *= z;
	z %= mod;
	if(p%2 == 0)
	    return z;
	z *= x;
	z %= mod;
	return z;
}

ll c(ll x, ll y){
	ll res = fac[x]*inv[y];
	res %= mod;
	res *= inv[x-y];
	res %= mod;
	return res;
}

int main()  {
	fac[0] = inv[0] = 1;
	for(int i=1 ;i <N ;i ++){
	    fac[i] = fac[i-1]*i;
	    fac[i] %= mod;
	    inv[i] = pw(fac[i],mod-2);
	}

	int t;
	cin>>t;
	while(t--){
	    scanf("%d%d%d",&n,&m,&k);
	    ll res =0;
	    for(int i=k ; i <= n ;i ++){
	        res += (c(n,i) * pw(m-1,n-i))%mod;
	        res %= mod;
	    }
	    printf("%lld\n",res);
	}
	return 0;
}
Tester's Solution

#include “bits/stdc++.h”
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“sse,sse2,sse3,ssse3,sse4,avx,avx2”)
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i–)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

Int F[MAX];
Int IF[MAX];

Int bpow(Int a, Int k)
{
Int res = 1;
while (k) {
if (k & 1) {
res *= a;
res %= MOD;
}
a *= a;
a %= MOD;
k /= 2;
}
return res;
}

Int C(int n, int k)
{
return F[n] * IF[k] % MOD * IF[n - k] % MOD;
}

int main(int argc, char* argv[])
{
// freopen(“in.txt”, “r”, stdin);
//ios::sync_with_stdio(false); cin.tie(0);

F[0] = 1;
FOR(i,1,MAX)
    F[i] = F[i - 1] * i % MOD;

FOR(i,0,MAX)
{
    IF[i] = bpow(F[i], MOD - 2);
}   

int t;
cin >> t;
FOR(tt,0,t)
{
    int n, m, k;
    cin >> n >> m >> k;
    Int res = 0;
    FOR(i,k,n + 1)
    {
        res += C(n, i) * bpow(m - 1, n - i);
        res %= MOD;
    }
    cout << res << endl;
}

cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

}

Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class ANGGRA{
	//SOLUTION BEGIN
	long mod = (long)1e9+7;
	long[][] fif;
	void pre() throws Exception{fif = fif((int)1e5+5);}
	void solve(int TC) throws Exception{
	    int n = ni();long m = nl();int k = ni();
	    long ans = 0;
	    for(int i = k; i<= n; i++)ans = add(ans, mul(C(fif, n, i), pow(m-1, n-i)));
	    pn(ans);
	}
	long C(long[][] fif, int n, int r){
	    if(n< 0 || n<r || r<0)return 0;
	    return (fif[0][n]*((fif[1][r]*fif[1][n-r])%mod))%mod;
	}
	long[][] fif(int mx){
	    mx++;
	    long[] F = new long[mx], IF = new long[mx];
	    F[0] = 1;
	    for(int i = 1; i< mx; i++)F[i] = (F[i-1]*i)%mod;
	    //GFG
	    long M = mod; 
	    long y = 0, x = 1; 
	    long a = F[mx-1];
	    while(a> 1){ 
	        long q = a/M;
	        long t = M; 
	        M = a%M;
	        a = t;
	        t = y;
	        y = x-q*y;
	        x = t;
	    } 
	    if(x<0)x+=mod;
	    IF[mx-1] = x;
	    for(int i = mx-2; i>= 0; i--)IF[i] = (IF[i+1]*(i+1))%mod;
	    return new long[][]{F, IF};
	}
	long mul(long a, long b){
	    if(a>=mod)a%=mod;
	    if(b>=mod)b%=mod;
	    a*=b;
	    if(a>=mod)a%=mod;
	    return a;
	}
	long add(long a, long b){
	    if(Math.abs(a)>=mod)a%=mod;
	    if(a<0)a+=mod;
	    if(Math.abs(b)>=mod)b%=mod;
	    if(b<0)b+=mod;
	    a+=b;
	    if(Math.abs(a)>=mod)a%=mod;
	    return a;
	}
	long pow(long a, long p){
	    long o = 1;
	    while(p>0){
	        if(p%2==1)o = (a*o)%mod;
	        a = (a*a)%mod;
	        p>>=1;
	    }
	    return o;
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new ANGGRA().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

10 Likes

Congrats for being 7* :smiley:

1 Like

Thanks :slight_smile:

4 Likes

T i+1 can take all distinct values irrespective of Ti.

T = { 2, 0 ,1 ,b } (say)
b can only posses values 1 or 0 actually T i+1 = T i or T i + 1 or 0

I am stuck here please help

7 star :heart_eyes: :clap::raised_hands:

3 Likes

https://www.codechef.com/viewsolution/26751247

Help needed in understanding , why my code is getting runtime error…?

T represents an array obtained by modulo m operation on every element of prefix sum of array A.
Consider y as Ai+1 term. Also it’s given that Ti is x. One way to obtain Ti+1 could be (x%m+y%m)%m… Now as y is an element of A it can take all values from 0 to m-1. And thus for any value of x we can have all possible values of Ti+1.

2 Likes

Why we are doing inv[i]=power(fac[i],mod-2) what does inv denote in setters code Confused…

Modular multiplicative inverse. Here is a nice explanation of the topic. :slightly_smiling_face:

tHANK YOU I was knowing it but I confused with inv by the way thankyiu so much

You’re welcome :slightly_smiling_face:

That is basically calculating (x!)^{-1} using fermat’s theorem stating that a^{p-1} = 1 \pmod p which implies a^{p-2} = a^{-1} \pmod p So we have (x!)^{p-2} = (x!)^{-1} \pmod p where p is a prime.

Read more on modular inverses and precomputing factorials and their inverses.

1 Like

Great editorial, very clearly it explained the T array part :fire:

1 Like