传送门：https://ac.nowcoder.com/acm/contest/9925/E
题意
有多少个满足1…n的全排列中，i > k时，$a_i>min_{j\in[i-k,i)}a_j。(n\ge10^7\;k\ge10^7)$
思路
[1，n]的区间里，因为i>k时才会有要求，所以将最小的数放在[1,k]当中。
设位置为pos，则
- [1,pos)的数随便放，有$C_{n-1}^{pos-1}*(pos-1)!$种方案
- (pos,n]的方法就又要要求了，假设方案数为$f[n-pos]$
所以我们得出
$$f[n]=\sum_{j=1}^{min(n,k)}C_{n-1}^{j-1}*(j-1)!*f[n-j]$$
这样我们就要递归出子问题了，即：
$$f[i]=\sum_{j=1}^{min(i,k)}C_{i-1}^{j-1}*(j-1)!*f[i-j]$$
所以暴力O(nk)的状态转移的话，就应该这样：
1
2
3
4
5
6
7
| void zhuanyi() {
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= min(i, k); j++) {
f[i] += f[i - j] \* C(i - 1, j - 1) \* fac[j - 1];
}
}
}
|
但是O(nk)是1e14的复杂度，这远远超标了，所以我们要优化以下，将转移方程优化为：
$$f[i]=(i-1)!*\sum_{j=1}^{min(i,k)}\frac{f[i-j]}{(i-j)!}$$
可以看到，等式右边就是一个前缀和，所以转移的过程中维护前缀和即可。
所以我们先预处理阶乘和阶乘逆元，在前缀和优化即可。
Code（345MS）
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
|
##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const ll mod = 998244353;
const int N = 1e7 + 10;
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
ll fac[N], invfac[N];
void init() {
fac[0] = 1;
for(int i = 1;i < N; i++) {
fac[i] = fac[i - 1] * i % mod;
}
invfac[N - 1] = quick_pow(fac[N - 1], mod - 2);
for(int i = N - 1;i >= 1; i--) {
invfac[i - 1] = invfac[i] * i % mod;
}
}
ll f[N];
ll sum[N];
void solve() {
init();
int n, k;
cin >> n >> k;
f[0] = sum[0] = 1;
for(int i = 1;i <= n; i++) {
f[i] = (sum[i - 1] - (i - k - 1 >= 0 ? sum[i - k - 1] : 0)) * fac[i - 1] % mod;
sum[i] = (sum[i - 1] + f[i] * invfac[i] % mod) % mod;
}
cout << (f[n] % mod + mod) % mod << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/18/2020-icpc-shanghai-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！