SRM686 Div1 600 CyclesNumber

发表于 | 分类于

Description

求出所有长度为\(n\)的置换的轮换数之和的\(m\)次方，对\(1000000007\)取模。

多组（\(1\ldots 300\)）询问，\(1\leq n\leq 10^5, 0\leq m\leq 300\)。

Solution

我们设\(x_i\)为置换\(i\)是否出现，那么答案就是\((\sum x_i)^m\)。

我们用第二类斯特林数把这个式子展开成下降幂，就得到了：\(\sum_{k = 0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\binom{\sum x_i}{k}\)。换言之所有有某\(k\)个轮换同时出现的方案数会对答案做出\(\begin{Bmatrix}m\\k\end{Bmatrix}k!\)的贡献。

那么考虑怎么计算所有有某\(k\)个轮换同时出现的方案数。我们考虑怎么去去除不需要的轮换，注意到我们可以加上一个虚点\(n + 1\)，然后把不需要的环顺次从右边断开，然后再顺次连上，最后和\(n + 1\)连上，这样的话我们就把这个方案数转化成了\(\begin{bmatrix}n + 1\\ k + 1\end{bmatrix}\)。

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
#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 <ctime>
typedef long long ll;
const ll ha = 1000000007LL;
using namespace std;
int s[100002][302], S[301][301], fac[302];
void process() {
  fac[0] = 1;
  for(int i = 1; i <= 301; i ++) {
    fac[i] = (ll)fac[i - 1] * (ll)i % ha;
  }
  s[0][0] = 1;
  for(int i = 1; i <= 100001; i ++) {
    s[i][0] = 0; if(i < 302) s[i][i] = 1;
    for(int j = 1; j < min(i, 302); j ++) {
      s[i][j] = s[i - 1][j - 1];
      s[i][j] += (ll)s[i - 1][j] * (ll(i - 1)) % ha;
      if(s[i][j] >= ha) s[i][j] -= ha;
    }
  }
  S[0][0] = 1;
  for(int i = 1; i <= 300; i ++) {
    S[i][1] = 1; if(i < 301) S[i][i] = 1;
    for(int j = 2; j < min(i, 301); j ++) {
      S[i][j] = S[i - 1][j - 1];
      S[i][j] += (ll(S[i - 1][j])) * (ll(j)) % ha;
      if(S[i][j] >= ha) S[i][j] -= ha;
    }
  }
}

class CyclesNumber {
public:
	vector <int> getExpectation(vector <int>, vector <int>);
};

vector <int> CyclesNumber::getExpectation(vector <int> n, vector <int> m) {
	process();
  vector<int> ret;
  for(int i = 0; i < n.size(); i ++) {
    int a = n[i], b = m[i];
    ll ans = 0;
    for(int j = 0; j <= b; j ++) {
      ll delta = (ll)fac[j] * (ll)S[b][j] % ha;
      delta = delta * (ll)s[a + 1][j + 1] % ha;
      ans = (ans + delta) % ha;
    }
    ret.push_back((int)ans);
  }
  return ret;
}