Combinatorics

• Problem
• Submissions
• Leaderboard
• Discussions
• Editorial

Meera bought a house on Mars, and plans to decorate it with chains of alien flowers. Each flower is either red (R) or blue (B), and Meera knows how many occurrences of RR, RB, BB, and BR she wants to see in a chain.

The diagram below shows a flower chain of length 10:

In this example, RR occurs 2 times (at positions 0 and 4), RB occurs 3 times (at positions 1, 5, and 7), BB occurs 1 time (at position 2), and BR occurs 3 times (at positions 3, 6, and 8).

Meera wants your help determining how many different chains with positive length can be made. Given A,B,C, and D, find the number of different chains having occurrences of RR,RB, BB and BR equal to inputs A,B,C, and D, respectively. As the answer can be very large, your printed output should be answer % (109+7).

Input Format

One line of space-separated, non-negative integers: A (occurrences of RR), B (occurrences of RB), C (occurrences of BB), and D (occurrences of BR), respectively.

Constraints

For 20% Points: 0≤A,B,C,D≤4

For 50% Points: 0≤A,B,C,D≤102

For 100% Points: 0≤A,B,C,D≤105

Output Format

Find the number of chains having A,B,C, and D occurrences of RR, RB, BB, and BR, respectively, and print the answer % (109+7).

Sample Input

1 1 2 1

Sample Output

5

Explanation

  The code goes here

/***********Template Starts Here***********/
#include <bits/stdc++.h>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod)x-=mod;
#define ODD(x) (((x)&1)==0?(0):(1))

using namespace std;

typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

#ifdef forthright48
     #include <ctime>
     clock_t tStart = clock();
     #define debug(args...) {dbg,args; cerr<<endl;}
    #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
    #define debug(args...)  // Just strip off all debug tokens
    #define timeStamp
#endif

struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
    vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    *X = x2; *Y = y2;
    return r2;
}

inline vlong modInv ( vlong a, vlong m ) {
    vlong x, y;
    ext_gcd( a, m, &x, &y );
    if ( x < 0 ) x += m; //modInv is never negative
    return x;
}

inline vlong power ( vlong a, vlong p ) {
    vlong res = 1, x = a;
    while ( p ) {
        if ( p & 1 ) res = ( res * x );
        x = ( x * x ); p >>= 1;
    }
    return res;
}

inline vlong bigmod ( vlong a, vlong p, vlong m ) {
    vlong res = 1 % m, x = a % m;
    while ( p ) {
        if ( p & 1 ) res = ( res * x ) % m;
        x = ( x * x ) % m; p >>= 1;
    }
    return res;
}

/***********Template Ends Here***********/
int mod = 1000000000 + 7;
vlong fact[2000000], inv[2000000];

void precal() {
    fact[0] = 1;
    FOR(i,1,1000000) {
        fact[i] = fact[i-1] * i;
        fact[i] %= mod;
    }

    FOR(i,0,1000000) {
        inv[i] = modInv( fact[i], mod );
    }
}

vlong combo ( int n, int k ) {
    if ( n == k ) return 1;
    if ( n == 0 ) return 0;
    if ( k == 0 ) return 0;

    int x = n - 1;
    int y = k - 1;

    vlong res = ( inv[x-y] * inv[y] ) % mod; ///Calculate nck(x,y)
    res *= fact[x];
    res %= mod;
    return res;
}

int solve ( int a, int b, int c, int d ) {
    if ( ABS(b-d) > 1 ) return 0;

    int tr = a + d;
    int tb = b + c;

    vlong res = 0;

    ///Start with R
    if ( b == d || b > d ) {
        res += combo ( tr + 1, d + 1 ) * combo ( tb, b );
        res %= mod;
    }

    ///Start with B
    if ( b == d || d > b ) {
        res += combo ( tr, d ) * combo ( tb + 1, b + 1 );
        res %= mod;
    }

    return res;
}

void solution() {

    int a, b, c, d;
    scanf ( "%d %d %d %d", &a, &b, &c, &d );

    printf ( "%d\n", solve ( a, b, c, d ) );

}

int main () {
    precal();

    solution();

    return 0;
}




The 5 flower chains having exactly 1,1,2, and 1 occurrences of RR, RB, BB and BR are:

Editorial by Mohammad Samiul Islam

We are given number of occurances of RR, RB, BB, BR (A,B,C,D) and we need to find number of strings which have same occurances.

A string is either of form {R}{B}{R}{B}... or {B}{R}{B}{R}... where {X} represents one or more of X.

Let use ignore RR and BB for now. How many strings can we make using RB and BR?

If B==D, then there are two ways:

• {R}{B}{R}...{R}, where {R} occurs D+1 times and {B} occurs B times.
• {B}{R}{B}...{B}, where {R} occurs D times and {B} occurs B+1 times.

If B==D+1, then there is one way: {R}{B}{R}{B}...{B}, where {R} occurs D+1 times and {B} occurs B times.

If B+1==D, then there is one way: {B}{R}{B}{R}...{R}, where {R} occurs D times and {B} occurs B+1 times.

If |D−B|>1, then there is no way.

Once we fix number ways we can place RB and BR, the rest is simple combinatorics. Each of {R} is a container that will contain one or more R and {B} is a container that will contain one or more B. For each way, we know number of containers and total number of flowers we want to place.

Number of ways we can place X items in Y containers such that each container contains atleast 1 item is (X−1Y−1).

Calculating binomial coefficient will take logarithm time here, but assuming we precalculated those, it takes O(1) time complexity.

Special Case

Seems like few people were having trouble with 0,0,0,0 input. The answer is 2. How? We can form the following two strings "R" and "B". Both of them has length 1 and contains no occurences of RR, RB,BB, BR.

/***********Template Starts Here***********/
#include <bits/stdc++.h>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod)x-=mod;
#define ODD(x) (((x)&1)==0?(0):(1))

using namespace std;

typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

#ifdef forthright48
     #include <ctime>
     clock_t tStart = clock();
     #define debug(args...) {dbg,args; cerr<<endl;}
    #define timeStamp debug ("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
#else
    #define debug(args...)  // Just strip off all debug tokens
    #define timeStamp
#endif

struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} };
//int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){
    vlong x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    *X = x2; *Y = y2;
    return r2;
}

inline vlong modInv ( vlong a, vlong m ) {
    vlong x, y;
    ext_gcd( a, m, &x, &y );
    if ( x < 0 ) x += m; //modInv is never negative
    return x;
}

inline vlong power ( vlong a, vlong p ) {
    vlong res = 1, x = a;
    while ( p ) {
        if ( p & 1 ) res = ( res * x );
        x = ( x * x ); p >>= 1;
    }
    return res;
}

inline vlong bigmod ( vlong a, vlong p, vlong m ) {
    vlong res = 1 % m, x = a % m;
    while ( p ) {
        if ( p & 1 ) res = ( res * x ) % m;
        x = ( x * x ) % m; p >>= 1;
    }
    return res;
}

/***********Template Ends Here***********/
int mod = 1000000000 + 7;
vlong fact[2000000], inv[2000000];

void precal() {
    fact[0] = 1;
    FOR(i,1,1000000) {
        fact[i] = fact[i-1] * i;
        fact[i] %= mod;
    }

    FOR(i,0,1000000) {
        inv[i] = modInv( fact[i], mod );
    }
}

vlong combo ( int n, int k ) {
    if ( n == k ) return 1;
    if ( n == 0 ) return 0;
    if ( k == 0 ) return 0;

    int x = n - 1;
    int y = k - 1;

    vlong res = ( inv[x-y] * inv[y] ) % mod; ///Calculate nck(x,y)
    res *= fact[x];
    res %= mod;
    return res;
}

int solve ( int a, int b, int c, int d ) {
    if ( ABS(b-d) > 1 ) return 0;

    int tr = a + d;
    int tb = b + c;

    vlong res = 0;

    ///Start with R
    if ( b == d || b > d ) {
        res += combo ( tr + 1, d + 1 ) * combo ( tb, b );
        res %= mod;
    }

    ///Start with B
    if ( b == d || d > b ) {
        res += combo ( tr, d ) * combo ( tb + 1, b + 1 );
        res %= mod;
    }

    return res;
}

void solution() {

    int a, b, c, d;
    scanf ( "%d %d %d %d", &a, &b, &c, &d );

    printf ( "%d\n", solve ( a, b, c, d ) );

}

int main () {
    precal();

    solution();

    return 0;
}