SRM671 div.1 300 BearCries

BearCries.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

ll dp[210][210][210];
ll const mod = 1000000007;

class BearCries {
public:
  int count(string message) {
    int N = message.size();
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    REP(i, N) REP(s, N) REP(p, N) {
      if (!dp[i][s][p]) continue;
      if (message[i] == ';') {
	dp[i+1][s+1][p] += dp[i][s][p];
	dp[i+1][s+1][p] %= mod;
	if (p > 0) {
	  dp[i+1][s][p-1] += p * dp[i][s][p];
	  dp[i+1][s][p-1] %= mod;
	}
      } else {
	dp[i+1][s][p] += p * dp[i][s][p];
	dp[i+1][s][p] %= mod;	
	if (s > 0) {
	  dp[i+1][s-1][p+1] += s * dp[i][s][p];
	  dp[i+1][s-1][p+1] %= mod;
	}
      }
    }
    return dp[N][0][0];
  }
};