Submission #3224143


Source Code Expand

#include <bits/stdc++.h>
#define N 2020
#define mod 1000000007
#define ll long long
using namespace std;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
  while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return f?x:-x;
}
ll frac[N*N];
ll fast_pow(ll x, ll y) {
  ll z = 1;
  for (; y; y >>= 1, x = x * x % mod) {
    if (y & 1) {
      z = z * x % mod;
    }
  }
  return z;
}
ll inv(ll x) {
  return fast_pow(x, mod - 2);
}
ll C(ll m, ll n) {
  return frac[m] * inv(frac[n]) % mod * inv(frac[m - n]) % mod;
}
int f[N][N];
int main(int argc, char const *argv[]) {

  frac[0] = 1;
  for (int i = 1; i <= 4000000; ++ i) {
    frac[i] = frac[i - 1] * i % mod;
  }

  int n = read(), k = read();

  if (k == 1) {
    return puts("1"), 0;
  }

  f[0][1] = 1;
  for (int j = 1; j <= n; ++ j) {
    for (int i = 0; i <= j; ++ i) {
      if (i < j) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
      if (j < n) f[i][j + 1] = (f[i][j + 1] + f[i][j] * C(i + (j + 1) * (k - 1) - 1, k - 2) % mod) % mod;
    }
  }
  printf("%lld\n", f[n][n] * frac[n] % mod);
  return 0;
}
/*
问题转化为拓扑计数问题

颜色顺序最后乘一个阶乘即可,现在要计算的是如下图的拓扑方案数。

| (0)->(0)->(0)->(0)->(0)
|  |    |    |    |    |
|  v    v    v    v    v
| (1)->(2)->(3)->(4)->(5)
|  |    |    |    |    |
|  v    v    v    v    v
| (1)  (2)  (3)  (4)  (5)
|  |    |    |    |    |
|  v    v    v    v    v
| (1)  (2)  (3)  (4)  (5)
|  |    |    |    |    |
|  v    v    v    v    v
| (1)  (2)  (3)  (4)  (5)

只需按照前两行从后往前转移即可。

f[i][j] 表示选了 i 个 0, j 种颜色的方案数。

每次转移相当于加入一个 0 或者加入一列。

|               .-- i ---.
|                (0)->(0)
|                 |    |
|                 v    v
|      (2)->(3)->(4)->(5)
|       |    |    |    |
|       v    v    v    v
|      (2)  (3)  (4)  (5)
|       |    |    |    |
|       v    v    v    v
|      (2)  (3)  (4)  (5)
|       |    |    |    |
|       v    v    v    v
|      (2)  (3)  (4)  (5)
|     `-------- j -------'

f[i+1][j] += f[i][j]
f[i][j+1] += f[i][j] * C(i+j*(k-1)+k-2, k-2)

ans = f[n][n] * n!

*/

Submission Info

Submission Time
Task F - Leftmost Ball
User swwind
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2335 Byte
Status AC
Exec Time 710 ms
Memory 47488 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 24
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
Case Name Status Exec Time Memory
0_00.txt AC 26 ms 33152 KB
0_01.txt AC 26 ms 33152 KB
0_02.txt AC 26 ms 33152 KB
0_03.txt AC 709 ms 47488 KB
1_00.txt AC 26 ms 33152 KB
1_01.txt AC 26 ms 33152 KB
1_02.txt AC 26 ms 33152 KB
1_03.txt AC 710 ms 47488 KB
1_04.txt AC 679 ms 47488 KB
1_05.txt AC 703 ms 47488 KB
1_06.txt AC 686 ms 47488 KB
1_07.txt AC 648 ms 47488 KB
1_08.txt AC 654 ms 47488 KB
1_09.txt AC 663 ms 47488 KB
1_10.txt AC 659 ms 47488 KB
1_11.txt AC 688 ms 47488 KB
1_12.txt AC 76 ms 38656 KB
1_13.txt AC 567 ms 47488 KB
1_14.txt AC 29 ms 33664 KB
1_15.txt AC 156 ms 41088 KB
1_16.txt AC 271 ms 43264 KB
1_17.txt AC 589 ms 47488 KB
1_18.txt AC 45 ms 36352 KB
1_19.txt AC 699 ms 47488 KB