P8474 「GLR-R3」立春

更好的阅读体验

题意：

设 $\sigma$ 为任意一个长度为 $n$ 的排列， $\tau (\sigma )$ 表示其中的逆序对个数，请求出

$$\sum _{\sigma }{2}^{\tau (\sigma )}$$

对 $(10^9+7)$ 取模的结果。

思路：

首先，长度为 $n+1$ 的任意排列等于长度为 $n$ 的任意排列在任意一个位置插入数字 $n+1$ 。

• 比如 $1,2,3$ 在任意一个位置插入 $4$ 变为 $1,2,3,41,2,4,31,4,2,34,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 }(2^{\tau (\sigma )}\times \sum _{i=0}^{n-1}{2}^i)$$

因为 ${\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$ ，考虑递推求解。

设 $an{s}_i$ 为长度为 $i$ 的值， $f_i$ 为 $2^{i+1}-1$ 。

有 $an{s}_i=an{s}_{i-1}\times f_{i-1},f_i=f_{i-1}\times 2+1$ 。

答案为 $an{s}_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;
}