Submission #3607874

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <chrono>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
/*---------------------------------------*/

const int MOD = 1000000007;

const int MAX_NM = 100;
const int MAX_KILL = 1000;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, m; cin >> n >> m;

  vector<int> a(1, 1), b(1, 1);
  int killa = 0, killb = 0;

  int temp1; cin >> temp1;
  killa += temp1;
  int a_index = 0;
  FOR(i, 1, n) {
    int temp2; cin >> temp2;
    killa += temp2;
    if (temp1 == temp2) ++a[a_index];
    else {
      a.push_back(1);
      ++a_index;
    }
    temp1 = temp2;
  }

  cin >> temp1;
  killb += temp1;
  int b_index = 0;
  FOR(i, 1, m) {
    int temp2; cin >> temp2;
    killb += temp2;
    if (temp1 == temp2) ++b[b_index];
    else {
      b.push_back(1);
      ++b_index;
    }
    temp1 = temp2;
  }

  vector<vector<long long> > dp(MAX_NM+1, vector<long long>(MAX_KILL+1, 0)); // 1-based & 0-based
  FOR(i, 1, MAX_NM+1) dp[i][0] = 1;
  REP(j, MAX_KILL+1) dp[1][j] = 1;
  FOR(i, 2, MAX_NM+1) {
    FOR(j, 1, MAX_KILL+1) {
      if (j-i >= 0) {
        dp[i][j] = (dp[i][j-i] % MOD) + (dp[i-1][j] % MOD);
        dp[i][j] %= MOD;
      } else dp[i][j] = dp[i-1][j];
    }
  }

  vector<vector<long long> > dpa(a_index+2, vector<long long>(MAX_KILL+1, 0)); // 1-based & 0-based
  FOR(i, 1, a_index+2) dpa[i][0] = 1;
  REP(j, MAX_KILL+1) dpa[1][j] = dp[a[0]][j];
  FOR(i, 2, a_index+2) {
    FOR(j, 1, MAX_KILL+1) {
      REP(k, j+1) {
        dpa[i][j] += (dpa[i-1][j-k] % MOD) * (dp[a[i-1]][k] % MOD);
        dpa[i][j] %= MOD;
      }
    }
  }

  vector<vector<long long> > dpb(b_index+2, vector<long long>(MAX_KILL+1, 0)); // 1-based & 0-based
  FOR(i, 1, b_index+2) dpb[i][0] = 1;
  REP(j, MAX_KILL+1) dpb[1][j] = dp[b[0]][j];
  FOR(i, 2, b_index+2) {
    FOR(j, 1, MAX_KILL+1) {
      REP(k, j+1) {
        dpb[i][j] += (dpb[i-1][j-k] % MOD) * (dp[b[i-1]][k] % MOD);
        dpb[i][j] %= MOD;
      }
    }
  }

  cout << (dpa[a_index+1][killb] * dpb[b_index+1][killa]) % MOD << "\n";
  return 0;
}

Submission Info

Judge Result