[Codeforces] D - Table with Letters - 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D - Table with Letters - 2
Source            : Codeforces
Category          : Data Structure, Two Pointer
Algorithm         : Two Pointer
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 400 + 5;  
  
int row;  
int column;  
int maxa;  
char grid[maxn][maxn];  
int mat[maxn][maxn];  
  
int subRectangleSum(int x1, int y1, int x2, int y2)  
{  
      int sum = mat[x2][y2] - mat[x2][y1 - 1] - mat[x1 - 1][y2] + mat[x1 - 1][y1 - 1];  
      return sum;  
}  
  
void solve()  
{  
      long long ans = 0;  
      for (int col_1 = 1; col_1 <= column; col_1++)  
      {  
            for (int col_2 = col_1 + 1; col_2 <= column; col_2++)  
            {  
                  int preRow = 1;  
                  vector <int> same(27, 0);  
                  for (int nxtRow = 1; nxtRow <= row; nxtRow++)  
                  {  
                        if (grid[nxtRow][col_1] == grid[nxtRow][col_2])  
                        {  
                              int val = grid[nxtRow][col_1] - 'a' + 1;  
                              while (preRow < nxtRow)  
                              {  
                                    int total_a = subRectangleSum(preRow, col_1, nxtRow, col_2);  
                                    if (total_a <= maxa) break;  
                                    if (grid[preRow][col_1] == grid[preRow][col_2])  
                                    {  
                                          int bad = grid[preRow][col_1] - 'a' + 1;  
                                          same[bad]--;  
                                    }  
                                    preRow++;  
                              }  
                              if (preRow < nxtRow) ans += same[val];  
                              same[val]++;  
                        }  
                  }  
            }  
      }  
      cout << ans << '\n';  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      freopen("input.txt", "r", stdin);  
      freopen("output.txt", "w", stdout);  
  
      cin >> row >> column >> maxa;  
      for (int i = 1; i <= row; i++)  
      {  
            for (int j = 1; j <= column; j++)  
            {  
                  cin >> grid[i][j];  
                  mat[i][j] = mat[i][j - 1] + (grid[i][j] == 'a');  
            }  
            for (int j = 1; j <= column; j++)  
            {  
                  mat[i][j] += mat[i - 1][j];  
            }  
      }  
      solve();  
}  

[Codemarshal] A. Tree Mania

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : A. Tree Mania
Source            : Codemarshal
                    SUB IUPC 2015
Category          : Combinatorics
Algorithm         : Prufer Code
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
static const long long mod = 1e9 + 7;  
  
long long binaryExpo(long long a, long long p, long long m)  
{  
      if (p <= 0) return 1 % m;  
      if (p == 1) return a % m;  
      if (p & 1) return (a % m * binaryExpo(a, p - 1, m)) % m;  
      long long ret = binaryExpo(a, p / 2, m);  
      return (ret % m * ret % m) % m;  
}  
  
long long modInv(long long a, long long m)  
{  
      return binaryExpo(a, m - 2, m);  
}  
  
long long fact[maxn];  
long long ifact[maxn];  
long long deg[maxn];  
  
void preCalc()  
{  
      fact[0] = 1LL;  
      ifact[0] = 1LL;  
      for (int i = 1; i < maxn; i++)  
      {  
            fact[i] = (1LL * i * fact[i - 1]) % mod;  
            ifact[i] = modInv(fact[i], mod);  
      }  
}  
  
long long nCr(int n, int r)  
{  
      if (n < r) return 0;  
      long long x = fact[n];  
      long long y = (ifact[r] * ifact[n - r]) % mod;  
      long long ncr = (x * y) % mod;  
      return ncr;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      preCalc();  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int n;  
            cin >> n;  
            int sum = 0;  
            for (int i = 1; i <= n - 2; i++)  
            {  
                  cin >> deg[i];  
                  sum += deg[i];  
            }  
            long long ans = 1;  
            int N = n - 2;  
            for (int i = 1; i <= n - 2; i++)  
            {  
                  long long x = nCr(N, deg[i] - 1);  
                  ans = (ans * x) % mod;  
                  N -= (deg[i] - 1);  
            }  
            int loop = 2 * (n - 1) - sum;  
            long long binomial = binaryExpo(2, loop - 2, mod);  
            long long totalTree = (ans * binomial) % mod;  
            cout << "Case " << tcase << ": " << totalTree << '\n';  
      }  
}