2014 TCO Wildcard 750 CountTables

发表于 | 分类于

Description

你有一个\(N\times M\)的网格和\(C\)种颜色，要求给每个格子染色，并且使得任意两行的染色方案不完全相同，任意两列也是。求方案数。

\(1\leq N, M, C\leq 4000\)。

Solution

TopCoder Arena真难用……

光限制列或者光限制行还算好做，但是同时限制就要掀桌子了。

所以我们不妨先考虑只去满足行的限制，这样的方案数为\(n!\binom{c^m}{n}\)，注意到这个东西的组合意义就是说明了（列意义上的）等价类至多有\(m\)个时的方案数，如果说至多有\(i\)个那么方案数就是\(n!\binom{c^i}{n}\)，不妨将其记为\(f_i\)。

现在我们很好做“至多”的方案数，那么要求“恰好”很显然就需要容斥力，，，注意到\(f_i = \sum_{j = 1}^i\begin{Bmatrix}i\\ j\end{Bmatrix}g_j\)，这里的\(g_j\)表示的是恰好有\(j\)个等价类的方案数，移项得\(g_i = f_i - \sum_{j = 1}^{i - 1}\begin{Bmatrix}i\\ j\end{Bmatrix}g_j\)，用这个式子递推就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>

using namespace std;
typedef long long ll;
const ll ha = 1000000007LL;
ll S[4005][4005];
class CountTables {
public:
  void process();
  ll pow_mod(ll, ll);
  ll inv(ll);
  ll C(ll, int);
	int howMany(int, int, int);
};

void CountTables::process() {
  // memset(S, 0, sizeof(S));
  S[1][1] = 1LL;
  for(int i = 2; i <= 4000; i ++) {
    S[i][1] = S[i][i] = 1;
    for(int j = 2; j < i; j ++) {
      S[i][j] = S[i - 1][j - 1];
      S[i][j] += (ll)j * S[i - 1][j] % ha;
      if(S[i][j] >= ha) S[i][j] -= ha;
    }
  }
}
ll CountTables::pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll CountTables::inv(ll x) {
  return pow_mod(x, ha - 2LL);
}
ll CountTables::C(ll n, int m) {
  if(n < (ll)m) return 0;
  ll ret = 1;
  for(int i = 1; i <= m; i ++) {
    ret = ret * ((n - (ll)i + 1LL) % ha) % ha;
    // ret = ret * inv(i) % ha;
  }
  return ret;
}
int CountTables::howMany(int n, int m, int c) {
  process();
  static ll g[4005];
  g[1] = C(c, n);
  for(int i = 2; i <= m; i ++) {
    ll f = C(pow_mod(c, i), n) % ha;
    for(int j = 1; j < i; j ++) {
      f = (f - (S[i][j] * g[j] % ha) + ha) % ha;
    }
    g[i] = f;
  }
  return (int)g[m];
}