11/6
10:41
OI

[牛客CSP-S集训营4]排列计数机 [斯特林数][DP][线段树]

排列计数机

神仙题….

(博客有点bug打不出斯特林数的括号,用S代替了)

首先我们要知道第二类斯特林数的一个式子:

x^m = \sum_{i=0}^m S(m,i) i! \binom{x}{i}

这个式子的意思是,m个不同球丢进x个盒子里,可以空的方案数,等于钦定i个非空方案数之和

所以只需要维护所有\binom{x}{i}就行了

考虑一个数数的式子,f_{i,j}表示前i个数,并且以i结尾的子段中,最大数有j个的数量

f_{i,j} = \sum_{k < i, A_k < A_i} f_{k, j - 1} 2^{ less_{k,i} }

less_{i,j}表示区间(i,j)中比A_i小的数数量

那么,最终对于每种最大值出现次数j,对答案的贡献是

\sum_{i} f_{i,j} 2^{less_{i,n+1}}

考虑用线段树优化这个O(n^3)的DP

线段树每个节点维护一个数组.令数组B_{A_i}=i,那么扫到第i个的时候,线段树叶子j的数组k,表示

\sum_x f_{B_j,x} 2^{less_{B_j,i}} \binom{x}{k}

考虑i-1 \rightarrow i时的影响.首先, > A_i的贡献是\times 2

我们考虑下面两个式子:

f_{i,j} = \sum_k f_{k,j-1}

\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}

我们现在线段树可以得到对于任意x的这个东西

\sum_k f_{k,j-1} \binom{j-1}{x}

所以按照组合数的式子求和,就可以更新新的叶子的值了

最后就可以借助S求答案了,具体看代码吧…….

不乱码的代码看这里

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1e5 + 233, P = 1e9 + 7;

int n, m, A[N], S[21][21];

struct Node {
  int val[21], tag;
  Node() {
    tag = 1;
    memset(val, 0, sizeof(val));
  }
} tree[N * 4];

#define ls(p) p << 1
#define rs(p) p << 1 | 1

inline void push(int p, int v) {
  for (int i = 0; i <= m; ++i)
    tree[p].val[i] = (long long)tree[p].val[i] * v % P;
  tree[p].tag = (long long)tree[p].tag * v % P;
}

inline void pushdown(int p) {
  if (tree[p].tag != 1) {
    push(ls(p), tree[p].tag);
    push(rs(p), tree[p].tag);
    tree[p].tag = 1;
  }
}

Node operator+(const Node &a, const Node &b) {
  Node ret;
  for (int i = 0; i <= m; ++i)
    ret.val[i] = (a.val[i] + b.val[i]) % P;
  return ret;
}

void mul(int p, int l, int r, int L, int R) {
  if (l <= L && r >= R)
    return push(p, 2);
  pushdown(p);
  int mid = (L + R) >> 1;
  if (l <= mid)
    mul(ls(p), l, r, L, mid);
  if (r > mid)
    mul(rs(p), l, r, mid + 1, R);
  tree[p] = tree[ls(p)] + tree[rs(p)];
}

Node query(int p, int l, int r, int L, int R) {
  if (l <= L && r >= R)
    return tree[p];
  pushdown(p);
  int mid = (L + R) >> 1;
  if (l <= mid && r > mid)
    return query(ls(p), l, r, L, mid)
      + query(rs(p), l, r, mid + 1, R);
  if (l <= mid)
    return query(ls(p), l, r, L, mid);
  if (r > mid)
    return query(ls(p), l, r, mid + 1, R);
}

void insert(int p, int x, Node y, int L, int R) {
  if (L == R) {
    tree[p].val[0] = y.val[0];
    for (int i = 1; i <= m; ++i)
      tree[p].val[i] = (y.val[i] + y.val[i - 1]) % P;
    return;
  }
  pushdown(p);
  int mid = (L + R) >> 1;
  if (x <= mid)
    insert(ls(p), x, y, L, mid);
  else
    insert(rs(p), x, y, mid + 1, R);
  tree[p] = tree[ls(p)] + tree[rs(p)];
}

int main() {
  // freopen("c.in", "r", stdin);
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i)
    A[i] = rd();

  S[0][0] = 1;
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= i; ++j)
      S[i][j] = (S[i - 1][j - 1] + (long long)j * S[i - 1][j]) % P;

  for (int i = 1; i <= n; ++i) {
    if (A[i] != n)
      mul(1, A[i] + 1, n, 1, n);
    Node ret;
    if (A[i] != 1)
      ret = query(1, 1, A[i] - 1, 1, n);
    ++ret.val[0];
    insert(1, A[i], ret, 1, n);
  }

  long long ans = 0, pow = 1;
  for (int i = 0; i <= m; ++i) {
    ans = (ans + S[m][i] * pow % P * tree[1].val[i]) % P;
    pow = pow * (i + 1) % P;
  }

  std::cout << ans << std::endl;

  return 0;
}