---
tags: VNOJ, THT, DP, Difference Array, Combinatorics, Inclusion Exclusion, SPyofgame
title: 🌱 Tin học trẻ 2021 - Vòng Khu vực - Bảng C - Hoán vị không bất động
author: Editorial-Slayers Team
license: Public domain
---
<style>
.markdown-body { max-width: 2048px; }
</style>
$\Huge \text{🌱 Tin học trẻ 2021 - Vòng Khu vực - Bảng C - Hoán vị không bất động}$
-----
###### 🔗 Link: [https://oj.vnoi.info/problem/tht21_kvc_permu](https://oj.vnoi.info/problem/tht21_kvc_permu)
###### 📌 Tags: `DP`, `Difference Array`, `Combinatorics`, `Inclusion Exclusion`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: @deptrai2k7, @matchamachiato , @FireGhost , [@Editorial Slayers Team](https://hackmd.io/@Editorial-Slayers/)
###### 📋 Content:
[TOC]
-----
## Phát biểu lại đề bài
Cho $2$ số nguyên $n$ và $q$
Cho $q$ đoạn $[l_i, r_i]$
Xét tập $S$ gồm các điểm $1, 2, \dots n$ mà thuộc vào ít nhất $1$ trong $q$ đoạn
Gọi điểm cố định là điểm ở vị trí $p$ cũng có giá trị $p$ của một hoán vị đang xét
Đếm số hoán vị bậc $n$ sao cho không tồn tại điểm cố định trong tập $S$
Không mất tính tổng quát, đưa các điểm trong tập $S$ thành các điểm $1, 2, \dots, k$ với $k = |S|$
Bài toán trở thành đếm số hoán vị bậc $n$ có $k$ điểm đầu không cố định
Để tính $k$ ta có thể dùng [different array](https://codeforces.com/blog/entry/78762#:~:text=A%20difference%20array%20can%20be,an%20O(N)%20computation.) hoặc các CTDL khác.
-----
### Code
> **Time:** $O(n + q)$
> **Space:** $O(n)$
> **Algo:** Implementation, Difference Array
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code
```cpp=
cin >> n;
memset(d, 0, sizeof(d[0]) * (n + 1)); /// diffrent array
int q;
cin >> q;
while (q-->0) /// for each required range
{
int l, r;
cin >> l >> r;
++d[l], --d[r + 1]; /// mark all range [l, r] as true
}
k = 0;
for (int i = 1; i <= n; ++i) /// for each position
{
d[i] += d[i - 1];
if (d[i] > 0) ++k; /// this position is in marked range
}
cin >> n;
```
:::
-----
## Hướng dẫn subtask 1-2
Ý tưởng đơn giản là thử từng hoán vị, và kiểm tra xem có tồn tại điểm cố định trong $k$ phần tử đầu hay không
Để thử từng hoán vị thì có thể sài `C++std::next_permutation`
-----
### Code
> **Time:** $O(n!)$
> **Space:** $O(n)$
> **Algo:** Brute-forces, Implementation, Math, Difference Array
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code
```cpp=
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int LIM = 1e5 + 15;
int fact[LIM];
int p[LIM];
int solve(int n, int k)
{
/// Initial Permutation
for (int x = 1; x <= n; ++x) p[x] = x;
int res = 0;
do
{
/// Check if the first k point have fixed point
for (int x = 1; x <= k; ++x)
if (p[x] == x) /// Found a fixed point
goto skip;
++res;
skip: {}
}
while (next_permutation(p + 1, p + n + 1)); /// For each permutation
return res;
}
int d[LIM];
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
int n, q;
cin >> n >> q;
memset(d, 0, sizeof(d));
while (q-->0)
{
int l, r;
cin >> l >> r;
++d[l], --d[r + 1];
}
int k = 0;
for (int i = 1; i <= n; ++i)
{
d[i] += d[i - 1];
if (d[i] > 0) ++k;
}
fact[0] = fact[1] = 1;
for (int x = 2; x <= n; ++x)
fact[x] = (1LL * x * fact[x - 1]) % MOD;
cout << solve(n, k);
return 0;
}
```
:::
-----
### Bonus
> Bạn có thể tối ưu để hàm chạy trong $O(k!)$ không ?
-----
## Hướng dẫn subtask 3-4
Đặt hàm quy hoạch động $f[n][k]$ là số hoán vị bậc $n$ không tồn tại điểm cố định trong $k$ phần tử đầu
Trường hợp $n = 0$, thì không có hoán vị nào, nên $f[0][k] = 0$
Trường hợp $k = 0$, thì cần đếm số hoán vị bậc $n$, nên $f[n][0] = n!$
Ngược lại, ta có $f[n][k] = f[n][k - 1] - f[n - 1][k - 1]$ là
- $f[n][k - 1]$ là số cách chọn giá trị tại vị trí $k$
- $f[n - 1][k - 1]$ là số cách chọn giá trị tại vị trí $k$ mà có thêm một điểm cố định
Kết quả bài toán là $f[n][k]$.
-----
### Code
> **Time:** $O(n \times k)$
> **Space:** $O(n^2)$
> **Algo:** DP, Combinatorics, Difference Array
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code
```cpp=
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int LIM = 5050;
const int LIM_2 = 1e5 + 15;
int fact[LIM_2];
int f[LIM][LIM];
int solve(int n, int k)
{
if (n <= 0) return 0;
if (k <= 0) return fact[n];
int &res = f[n][k];
if (res != -1) return res;
res = solve(n, k - 1) - solve(n - 1, k - 1);
if (res < 0) res += MOD;
return res;
}
int d[LIM_2];
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
int n, q;
cin >> n >> q;
memset(d, 0, sizeof(d));
while (q-->0)
{
int l, r;
cin >> l >> r;
++d[l], --d[r + 1];
}
int k = 0;
for (int i = 1; i <= n; ++i)
{
d[i] += d[i - 1];
if (d[i] > 0) ++k;
}
fact[0] = fact[1] = 1;
for (int x = 2; x <= n; ++x)
fact[x] = (1LL * x * fact[x - 1]) % MOD;
memset(f, -1, sizeof(f));
cout << solve(n, k);
return 0;
}
```
:::
-----
### Bonus
> Bạn có thể làm trong $O(n \times k)$ thời gian nhưng chỉ với $O(n)$ bộ nhớ không ?
-----
## Hướng dẫn subtask 5
Gọi $G[x]$ là số hoán vị bậc $n$ có ít nhất $x$ điểm cố định trong $k$ vị trí đầu tiên
Ta có $G[x] = C_k^x \times (n - x)!$
- Với $C_k^x$ là số cách chọn một hoán vị có $x$ điểm cố định trong $k$ phần tử đầu
- Và $(n - x)!$ là số cách chọn $n - x$ phần tử còn lại chưa được chọn (có thể có điểm cố định)
Gọi $F[k]$ là số hoán vị bậc $n$ không có bất cứ điểm cố định nào xuất hiện tại $k$ vị trí đầu tiên
- Dễ thấy được $F[k] = G[0] - G[1] + G[2] - G[3] + G[4] - ... \pm G[k]$
- Một cách tổng quát $F[k] = \underset{0 \leq i \leq k}{\Large \Sigma} \normalsize G[i] \times (-1)^i$
Kết quả bài toán là $F[k]$.
-----
Có $\large \binom{k}{x} \normalsize = \Large \frac{k!}{x! (k - x)!} \normalsize = k! \times x!^{-1} \times (k-x)!^{-1}$
Vì $M = 10^9 + 7$ là một số nguyên tố nên $x^{-1} \equiv x^{M-2} \pmod M$
Ngoài ra ta cũng có thể tính $x^{-1}$ dựa trên $p^{-1}$ với $p \equiv M \pmod x$
Ta có thể tiền xử lí các giá trị $n!$ và $n!^{-1}$ để tính $C_k^x$ trong $O(\log n)$ hoặc $O(1)$
-----
### Code
> **Time:** $O(n)$
> **Space:** $O(n)$
> **Algo:** DP, Difference Array, Combinatorics, Inclusion Exclusion
> [color=lightgreen]
:::success
:::spoiler SPyofgame Code
```cpp=
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int LIM = 1e5 + 15;
const int MOD = 1e9 + 7;
/// Combinatorics Precalculation
/// Complexity: Linear in time and space
int fact[LIM]; /// n! % MOD
int invs[LIM]; /// n^(-1) % MOD
int tcaf[LIM]; /// n!^(-1) % MOD
/// Precalculate first n number
void precal(int n)
{
fact[0] = fact[1] = 1;
invs[0] = invs[1] = 1;
tcaf[0] = tcaf[1] = 1;
for (int x = 2; x <= n; ++x)
{
/// n! = n * (n - 1)!
/// n^(-1) = floor(MOD / n) * (MOD % x)^(-1)
/// n!^(-1) = n^(-1) * (n-1)!^(-1)
fact[x] = (1LL * x * fact[x - 1]) % MOD;
invs[x] = MOD - 1LL * (MOD / x) * invs[MOD % x] % MOD;
tcaf[x] = (1LL * invs[x] * tcaf[x - 1]) % MOD;
}
}
/// Combinatorics Query
/// Complexity: Linear in time and constant space
/// Query for nCk = n! / k! / (n-k)!
int nck(int n, int k)
{
/// nCk = n! * k!^(-1) * (n-k)!^(-1)
return 1LL * fact[n] * tcaf[k] % MOD * tcaf[n - k] % MOD;
}
/// Get the needed input
/// Complexity: Linear in time and space
int d[LIM];
void input(int &n, int &k)
{
cin >> n;
memset(d, 0, sizeof(d[0]) * (n + 1)); /// diffrent array
int q;
cin >> q;
while (q-->0) /// for each required range
{
int l, r;
cin >> l >> r;
++d[l], --d[r + 1]; /// mark all range [l, r] as true
}
k = 0;
for (int i = 1; i <= n; ++i) /// for each position
{
d[i] += d[i - 1];
if (d[i] > 0) ++k; /// this position is in marked range
}
}
/// Number of permutation of n elements with non of the first k positions is fixed
/// Complexity: Linear in time and constant space
ll solve(int n, int k)
{
/// G[x] = Number of permutation of n elements with atleast (x) fixed point appear in first k position
/// G[x] = A * B
/// A = kCx = number of way to select (x) fixed point in first k position
/// B = (n-x)! = number of way to select the rest (n - x) elements (can also be fixed point)
///
/// F[x] = Number of permutation of n elements with non of the first x positions is fixed
/// Inclusion-Exclusion Formula:
/// F[x] = G[0] - G[1] + G[2] - G[3] + G[4] - ... ± G[x]
///
ll res = 0;
for (int x = 0; x <= k; ++x)
{
int v = 1LL * nck(k, x) * fact[n - x] % MOD;
res += (x & 1) ? -v : +v;
}
/// Take modulo
res %= MOD;
if (res < 0) res += MOD;
return res;
}
/// Problem solvin in linear time and space
int main()
{
// file("Test");
ios::sync_with_stdio(NULL);
cin.tie(NULL);
int n, k;
input(n, k);
precal(n);
cout << solve(n, k);
return 0;
}
```
:::
-----
### Bonus
> Với modulo nguyên tố đủ nhỏ thì bạn có có thể giải với $0 \leq k \leq n \leq 10^{12}$ không?
> Với modulo nguyên tố đủ nhỏ thì bạn có có thể giải với $0 \leq k \leq n \leq 10^{18}$ không?
> Bạn có thể chứng minh công thức $F[k] = G[0] - G[1] + G[2] - G[3] + G[4] - ... \pm G[k]$ hay không?
> Bạn có thể giải với $Q$ truy vấn $(n, k)$ trong bao lâu?
Sign in with Wallet
Connect another wallet