设$f[i]$为长度为$i$的序列（不是排列）中计数器的大小。假设现在已知$f[i-1]$
那么第$i$位与前面的相对大小关系一共有i种
1.第$i$位相对大小为i，对计数器没有任何影响，直接转移 $f[i]=f[i-1]$
2.第$i$位相对大小小于$i$ (即$1~i-1$)，设为$j$，那么计数器的值就需要增加$2^{j-1}$ （可以拿几个数试一下），对于前$i-1$个数，他们的顺序有$（i-1）！$种，所以$ f[i]=f[i-1]+2^{j-1}*(i-1)!$
综上，
$f[i]=f[i-1]+(f[i-1]+2^{1-1}*(i-1)!)+(f[i-1]+2^{2-1}*(i-1)!)+(f[i-1]+2^{3-1}*(i-1)!)...+(f[i-1]+2^{i-1-1}*(i-1)!)$
发现$2$的多少次方是一个等比数列，可以直接用前$i-1$项和公式求出来，剩下$i$个$f[i-1]$相加
最终得到$f[i]=f[i-1]*i+(2^{i-1}-1)*(i-1)!$
答案即为$f[n]/n!$
#include <bits/stdc++.h> using namespace std; #define N 100010 #define ll long long const int mod = (int)1e9 + 7; inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } ll qpow(ll a, ll b){ ll sum = 1; while(b){ if(b & 1) sum = (sum * a) % mod; a = (a * a) % mod; b >>= 1; } return sum; } ll f[N]; ll n; int main(){ // freopen("seventeen10.in", "r", stdin); // freopen("seventeen10.out", "w", stdout); n = read(); ll num = 1, tot = 1; for(ll i = 1; i <= n; i++){ f[i] = (f[i - 1] * i % mod + (tot - 1) * num % mod) % mod; tot = (tot << 1) % mod; num = (num * i) % mod; } cout << f[n] * qpow(num, mod - 2) % mod << endl; return 0; }
部分转载于大佬的博客