Subpermutation

$\ n$ 的排列是一个长度为 $\ n$ 的序列，其中从 $\ 1$ 到 $\ n$ 的每个数字都只出现一次。 $\ n$ 的全排列是将 $\ n$ 的所有排列按字典顺序连接成一个序列的序列。如果 $\ p_i<q_i$ 其中 $\ i$ 是满足 $p_i≠q_i$ 的最小索引，则序列 $p_1,p_2,...,p_n$ 在字典上小于 $\ q_1,q_2,...,q_n$ 。

以下是此问题中使用的一些符号：

- $\ p_n$ ： $\ n$ 的全排列。例如， $\ p_3=\{1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1\}$ 。
- $\ S_n$ ： $\ n$ 的所有排列的集合。例如， $\ S_3=\{\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2 ,1\}\}$ 。
- $\ f(s,t)$ ： $\ s$ 中等于 $\ t$ 的连续子序列的数量。例如， $\ f(\{1,2,12,1,2\},\{1,2\})=2$ 。

现在给定 $\ n$ 和 $\ m$ ，请计算 $\ ∑_{t∈S_m}f(p_n,t)\ modulo\ 10^9+7$ 。

#include<bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9+7,N = 1e6+6; int f[N],g[N]; void init(){ f[1] = g[1] = g[0] = f[0] = 1; for(int i = 2; i < N; i++){ f[i] = f[i-1]*i%mod; g[i] = (g[i-1]+1)*i%mod; } } signed main(){ int t; cin >> t; init(); while(t--){ int n,m; cin >> n >> m; int ans = ((n*f[m]%mod)*f[n-m]%mod-g[m]+f[m]+mod)%mod; cout << ans << '\n'; } }

详情