cqx에서 온 dp신제.

#include 
#include 
#include 

#define maxlen 100
#define maxn   205
#define base   1000000

typedef int bn[maxlen];

bn buf;
bn dp[maxn][maxn];
int B[maxn];
int G[maxn];

void add (bn p, bn q, int k)
{
  if (!k || !q[0] || !q[q[0]]) return;
  bn x;
  int i;
  memset (x, 0, sizeof (x));
  x[0] = p[0] > q[0] ? p[0] : q[0];
  for (i = 1; i <= x[0]; ++i)
    x[i] = p[i] + q[i] * k;
  for (i = 1; i <= x[0]; ++i)
    if (x[i] >= base)
      x[i + 1] += x[i] / base, x[i] %= base;
  if (x[x[0] + 1]) ++x[0];
  memcpy (p, x, sizeof (bn));
}

int cmper (const void *i, const void *j)
{
  return *(int *)i - *(int *)j;
}

int main()
{
  FILE *fin  = fopen ("ball.in" , "r");
  FILE *fout = fopen ("ball.out", "w");

  int n, k, Gk = 0, Bk = 0, i, j;
  bn ans;

  fscanf (fin, "%d%d", &n, &k);
  for (i = 1; i <= n; ++i)
    fscanf (fin, "%d", &B[i]);
  for (i = 1; i <= n; ++i)
    fscanf (fin, "%d", &G[i]);
  qsort (B + 1, n, sizeof (B[0]), cmper);
  qsort (G + 1, n, sizeof (G[0]), cmper);

  dp[0][0][0] = 1, dp[0][0][1] = 1;
  for (i = 1; i <= n; ++i)
    {
      for (; G[Gk] <= B[i] && Gk < i; ++Gk);
      for (; B[Bk] <  G[i] && Bk < i; ++Bk);
      for (j = i - Gk; j <= Bk; ++j)
        {
          memcpy (dp[i][j], dp[i - 1][j - (B[i] < G[i])], sizeof (bn));
          add (dp[i][j], dp[i - 1][j - 1], i - j + Bk - Gk);
          add (dp[i][j], dp[i - 1][j    ],     j - Bk + Gk);
        }
    }

  memset (ans, 0, sizeof (ans));
  for (i = 0; i <= k; ++i)
    add (ans, dp[n][i], 1);
  
  fprintf (fout, "%d", ans[ans[0]]);
  for (; --ans[0] > 0; )
    fprintf (fout, "%06d", ans[ans[0]]);

  fclose (fin);
  fclose (fout);
  return 0;
}