Friday, December 15, 2017

Comilla University CSE Fiesta 2017 - D. Unique String

Problem Statement:

There are 3 types of letters available. They are A, B and C. You are given the frequencies of them. You have to make a word with all of them but have to maintain one condition that letter A and B will not be adjacent to each other. How many different words you can make maintaining the condition.
For example, if the frequencies of letter A, B and C are 1, 1 and 2, the answer will be 6. The words are ACCB, ACBC, CACB, BCAC, BCCA and CBCA.

Input

First line of input contains the number of test cases T (1<= T <= 100000). Next T lines describe the case. Each case contains three integers x, y and z where x denotes the frequency of A, y denotes the frequency of B and z denotes the frequency of C (0 <= x, y, z <= 100000 && min(x, y) < 3 && (x + y + z) ≥ 1).

Output

For each test case, output a single line contains “Case X: Y” without any quote where X denotes the number of test cases and Y denotes the answer of the problem. Answer could be very large so output the answer modulo 1000000007.
Sample Input / Output:

2
1 1 1
1 1 2
Case 1: 2
Case 2: 6


Solution:

First Hint is min(x, y) < 3
So, we can handle the cases of unique string by hand.

Here Is the code of Mine ( Solution Description will be updated Later ):



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*input
2
1 1 1
1 1 2
*/

#include <bits/stdc++.h>
using namespace std;

#define mx 1000005
#define ll long long
#define MOD 1000000007
ll fact[mx], inv[mx];
ll nCr(int n, int r)
{
 return  1ll * (fact[n] * inv[r] % MOD) * inv[n-r] % MOD;
} 
ll bigmod(ll a, ll p)
{
 if(p==0) return 1;
 if(p&1) return a * bigmod(a, p-1) % MOD;
 ll mo = bigmod(a, p/2);
 return mo * mo % MOD;
}
ll val(int b, int c)
{
 return (1ll * (fact[b+c] * inv[b] % MOD) * inv[c]) % MOD; 
}
int fun0(int a, int b, int c)
{
 return val(b, c);
}
ll fun1(int a, int b, int c)
{
 int n = a + b + c;
 ll ans = 0;
 if(n >= 3){
  if(c >= 2) ans = (ans + 1ll * (n-3+1) * val(b, c-2) % MOD) % MOD;
  if(c >= 1) ans = (ans + 2ll * val(b, c-1) % MOD) % MOD;
 }
 return ans % MOD;
}

ll fun2(int a, int b, int c)
{
 int n = a + b + c;
 ll ans = 0;
 if(n >= 4){
  if(c >= 2) ans = (ans + 1ll * (n-4+1) * val(b, c-2) % MOD) % MOD;
  if(c >= 1) ans = (ans + 2ll * val(b, c-1) % MOD) % MOD;
  // hi
  if(c >= 2) ans = (ans + val(c-2, b)) % MOD;
 }
 if(n >= 5){
  if(c >= 3) ans = (ans + 1ll * (n-5+1) * val(b, c-3) % MOD) % MOD;
  if(c >= 2) ans = (ans + 2ll * val(b, c-2) % MOD) % MOD;
 }
 ll k = n-6+1;
 k = (k * (k+1) / 2 ) % MOD; 
 if(n >= 6){
  if(c >= 4) ans = (ans + k * val(b, c-4) % MOD) % MOD;
  if(c >= 3) ans = (ans + 2ll * (n-5+1) * val(b, c-3) % MOD) % MOD;
 }
 return ans;
}
int main()
{
 fact[0] = inv[0] = 1;
 for(int i = 1; i<mx; i++)
 {
  fact[i] = fact[i-1] * i % MOD;
  inv[i] = inv[i-1] * bigmod(i, MOD-2) % MOD;
 }
 // cout << nCr(5, 2) << endl;

 int t, tst = 1;
 scanf("%d", &t);
 while(t--)
 {
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  if(a > b) swap(a, b);
  ll ans = 0;
  if(a==0) ans = fun0(a, b, c);
  else if(a==1) ans = fun1(a, b, c);
  else ans = fun2(a, b, c);
  printf("Case %d: %lld\n", tst++, ans);
 }
 return 0;
}

**Happy Coding**
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Comilla University CSE Fiesta 2017 - D. Unique String

Problem Statement: There are 3 types of letters available. They are A, B and C. You are given the frequencies of them. You have to mak...