kurarrr's memooo

主に競プロ備忘録

第4回ドワンゴ 予選 C - Kill/Death (500)

解法

前提知識 分割数
蟻本にも載ってる.

この問題は,X=sum(death)=sum(相手チームのkill)とすると,
kill数が全員同じ -> sum(death_i) = X, death_i は昇順の通り数 -> すなわち分割数,DPで出せる
kill数が全員違う -> sum(death_i) = X, death_i の順番なしの通り数 -> コンビネーション,DPで出せる

なので,kill数が同じ人を同じグループとして,分割数をあらかじめ計算しておき,
dp[j][i] := (jグループまでで和iを分割する通り数) とおくと,(j,iが逆なのは分割数の計算をdp[和 i][人数 j]としたから)
dp[j][i] = sum_(0<=k<=i) (dp[j-1][i-k] * (和kをグループjで分割する分割数))
という漸化式が生える.
O(N*(sum(kill))2) = O(108)ぐらいでちょっと危うそうだが間に合った.

なお,より良い解法があって,
こちらはkill数が同じプレイヤーが複数いた時,昇順になるので後ろのプレイヤーにもdeathを配るというもの.
すなわち,dp[i][j] := (i人までにjを分割する通り数) と置いて,

後ろにkill数が同じ人がいない時,
dp[i][j] = dp[i-1][j] + dp[i][j-1]から,

後ろにkill数が同じ人が自分含めk人いる時,
dp[i][j] = dp[i-1][j] + dp[i][j-k]
(上とまとめられる)
また, j < k の時(和よりも後ろにいる人数の方が多い時), 自分は0しか取れないので
dp[i][j] = dp[i-1][j]
となる.天才か.

メモ

区別あり/なしの和の分割の話は覚えておきたい.
分割数を覚えてなかったので,その前提がないと難しそう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 102, MAX_SUM = 1003;

ll part_dp[MAX_SUM][MAX_N],dp[MAX_N][MAX_SUM];

void prepare(){
  REP(i,1,MAX_SUM) part_dp[i][1] = 1LL;
  rep(i,MAX_N) part_dp[0][i] = 1LL;
  REP(i,1,MAX_SUM) REP(j,2,MAX_N){
    if(j>i) part_dp[i][j] = part_dp[i][i];
    else part_dp[i][j] = (part_dp[i-j][j] + part_dp[i][j-1]) % lmod;
  }
}

ll solve(vector<int> &kill,int death){
  int depth[MAX_N];
  fill(depth,depth+MAX_N,0);
  int prev = kill[0], N = kill.size(), cnt = 0;
  depth[cnt]++;
  if(N>1){
    REP(i,1,N){
      if(kill[i]==prev) depth[cnt]++;
      else{
        prev = kill[i];
        cnt++;
        depth[cnt]++;
      }
    }
  }
  cnt++;
  fill(dp[0],dp[MAX_N-1],0LL);
  dp[0][0] = 1LL;
  REP(j,1,cnt+1) REP(i,0,death+1){
    rep(k,i+1) (dp[j][i] += dp[j-1][i-k] * part_dp[k][depth[j-1]]) %= lmod;
    // cout << j << "," << i << " " << dp[j][i] << endl;
  }
  // cout << dp[cnt][death] << endl;
  return dp[cnt][death];
}

int main(){
  vector<int> a,b;
  int N,M; cin >> N >> M;
  int a_sum = 0,b_sum = 0;
  rep(i,N){
    int k; scanf("%d",&k);
    a.pb(k);
    a_sum += k;
  }
  rep(i,M){
    int k; scanf("%d",&k);
    b.pb(k);
    b_sum += k;
  }
  prepare();
  cout << solve(a,b_sum) * solve(b,a_sum) % lmod << endl;
  return 0;
}