P8474 「GLR-R3」立春 题解
俗话说的好：“打表出奇迹”，所以我们这一题打表计算。
其实确实可以打表来找规律。通过打表，我们可以获得如下的结果：
1 1
2 3
3 21
4 315
5 9765
…… ……
然后观察可得：
\[1 \times 3 = 1 \times (2^2 - 1) = 3
\]
\[3 \times 7 = 3 \times (2^3 - 1) = 21
\]
\[21 \times 15 = 21 \times (2^4 - 1) = 315
\]
\[315 \times 31 = 315 \times (2^5 - 1) = 9765
\]
于是可以猜测，设 \(f_i\) 为 \(n = i\) 时的答案，则有 \(f_i = f_{i - 1}\times (2^i - 1)\)。
这样就可以 \(O(n)\) 递推了。
但是我们还需要知道的是，为什么是这样的关系。
假设我们已经知道了 \(n = i - 1\) 时的答案，现在需要求出 \(n = i\) 时的答案。
显然，一个 \(i\) 的排列可以向一个 \(i - 1\) 的排列中的一个位置插入数 \(i\) 来得到，由于一个 \(i - 1\) 的排列中不会有大于 \(i\) 的数，所以对于任意一个 \(i - 1\) 的排列，从后往前插入数 \(i\) 依次会增加 \(0,1,2,\dots,i - 1\) 个逆序对。
所以，\(f_i = f_{i - 1} \times (2^0,2^1,2^2,\dots,2^{i - 1}) = f_{i - 1} \times (2^i - 1)\)。
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n;
ll ans = 1, bit = 4;
int main(){
scanf("%d",&n);
for(int i = 2; i <= n; i++, (bit <<= 1) %= MOD){
(ans *= (bit - 1)) %= MOD;
}
printf("%lld\n",ans);
return 0;
}