题意：
设 \(\sigma\) 为任意一个长度为 \(n\) 的排列， \(\tau(\sigma)\) 表示其中的逆序对个数，请求出
\[\sum_\sigma 2^{\tau(\sigma)} \]对 \((10^9+7)\) 取模的结果。
思路：
首先，长度为 \(n+1\) 的任意排列等于长度为 \(n\) 的任意排列在任意一个位置插入数字 \(n+1\) 。
- 比如 \(1,2,3\) 在任意一个位置插入 \(4\) 变为 \(1,2,3,4 \quad 1,2,4,3 \quad 1,4,2,3 \quad 4,1,2,3\) 四种情况，其他排列同理。
然后考虑向长度为 \(n-1\) 的一个排列 \(a_1 ,a_2,a_3,\dots ,a_{n-1}\) 插入数字 \(n\) 后逆序对个数的变化。
因为数字 \(n\) 大于排列 \(a\) 的任意一个数，所以 \(n\) 只会和在 \(n\) 后面的数字形成新的逆序对，并且原来的逆序对不变。
设 \(\beta\) 为排列 \(a\) 在任意一个位置插入 \(n\) 后形成的新排列。
有
\[\sum_\beta 2^{\tau(\beta)} = \sum_{i=0}^{n-1} 2^{\tau(a)+(n-i)}=\sum_{i=0}^{n-1} 2^{\tau(a)+i}=2^{\tau(a)} \times \sum_{i=0}^{n-1} 2^i \]接下来求 \(\sum_\sigma 2^{\tau(\sigma)}\) 。
设 \(\delta\) 为为任意一个长度为 \(n\) 的排列。
设 \(\sigma\) 为任意一个长度为 \(n-1\) 的排列。
设 \(\beta\) 为排列 \(\sigma\) 在任意一个位置插入 \(n\) 后形成的新排列。
所以：
\[\sum_\delta 2^{\tau(\delta)}=\sum_\sigma \sum_\beta 2^{\tau(\beta)} =\sum_\sigma \Big (2^{\tau(\sigma)} \times \sum_{i=0}^{n-1} 2^i \Big ) \]因为 \(\sum_{i=0}^{n-1} 2^i\) 为定值所以将 \(\sum_{i=0}^{n-1} 2^i\) 移出得：
\[\sum_\delta 2^{\tau(\delta)}=\sum_\sigma 2^{\tau(\sigma)} \times \sum_{i=0}^{n-1} 2^i=\sum_\sigma 2^{\tau(\sigma)} \times (2^n-1) \]因为 \(2^n-1=(2^{n-1}-1)\times 2-1\) ，考虑递推求解。
设 \(ans_i\) 为长度为 \(i\) 的值， \(f_i\) 为 \(2^{i+1}-1\) 。
有 \(ans_i=ans_{i-1} \times f_{i-1}\ , \ f_i=f_{i-1} \times 2 + 1\) 。
答案为 \(ans_n\) 。
\(Code\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int f[10000001];
int ans[10000001];
signed main(){
int n;
cin>>n;
ans[1]=1;
ans[2]=3;
f[2]=7;
for(int i=3; i<=n; i++)
{
f[i]=f[i-1]*2+1,f[i]%=mod;
ans[i]=ans[i-1]*(f[i-1])%mod;
}
cout<<ans[n]<<endl;
return 0;
}