( ext{Update})(2019.10.05):
- 递推公式推法更详细；
- 通项公式更新详细版；
- 单位矩阵的推法更加详细。
特别鸣谢 @Smallbasic 苣佬，是他教会了我推递推公式和通项公式。
吐槽：来自同机房巨佬的嘲讽——这道题这么简单，观察法显然可得通项公式
题目分析：
-
分析题面，原题意思如下：
从(n)个互不相同的数中取出某些数，将这些数分成两个集合(A,B)，这两个集合满足两个条件：
-
$A $ 集合中的最大的数小于 (B)集合中最小的数
-
$A,B eq emptyset $
求共有多少种分法(结果对 (10^9+7) 取模)
-
-
显然可以发现这题是一道组合数学的题，先手算 (n leq 10) 的数据，在找规律推出公式。我给一下我的思路：
-
当 (n=2) 时，答案显然为1
-
当 (n=3) 时，设这些数为 (a_1,a_2,a_3) ,不妨设 (a_1<a_2<a_3)
- 当取3个数时，有以下分法：[A={a_1 },B={a_2,a_3} \ A={a_1,a_2},B={a_3} ]
共 (C^3_3 imes (3-1)=2) 种
- 当取2个数时，有以下分法：
[ A={a_1},B={a_2}\ A={a_1},B={a_3}\ A={a_2},B={a_3} ]共 (C_3^2 imes (2-1)=3) 种
综上，当 (n=3) 时，有 (C^3_3 imes (3-1)+C_3^2 imes (2-1)=5) 种分法。
- 当取3个数时，有以下分法：
-
当 (n=4) 时，设这些数为 (a_1,a_2,a_3,a_4) ,不妨设 (a_1<a_2<a_3<a_4)
- 当取4个数时，有以下分法：
[ A={a_1},B={a_2,a_3,a_4}\ A={a_1,a_2},B={a_3,a_4}\ A={a_1,a_2,a_3},B={a_4} ]共 (C^4_4 imes (4-1)=3) 种
-
当取3个数时，有以下分法：
[A={a_1},B={a_2,a_3}\ A={a_1},B={a_2,a_4}\ A={a_1},B={a_3,a_4}\ A={a_2},B={a_3,a_4}\ A={a_1,a_2},B={a_3}\ A={a_1,a_2},B={a_4}\ A={a_1,a_3},B={a_4}\ A={a_2,a_3},B={a_4} ]共 (C^3_4 imes (3-1)=8) 种
-
当取2个数时，有以下分法：
[A={a_1},B={a_2}\ A={a_1},B={a_3}\ A={a_1},B={a_4}\ A={a_2},B={a_3}\ A={a_2},B={a_4}\ A={a_3},B={a_4} ]共 (C^2_4 imes (2-1)=6) 种
综上，当 (n=4) 时，有 (C^4_4 imes (4-1)+C^3_4 imes (3-1)+C^2_4 imes (2-1)=17) 种分法。
-
通过数学归纳（
找规律），可得公式：[F(n)=sum_{i=1}^{n-1}C^{i+1}_n cdot i ]
具体实现的代码就不写了，其他dalao有写。
时间复杂度：(O(n^2))
空间复杂度：(O(n^2))
预计得分：40 points
-
-
考虑优化。
发现公式中的瓶颈在于如何快速处理组合数，于是开始推递推公式：
[]egin{aligned}
& F(n+1)-2F(n)
& =sum_{i=1}^{n}C^{i+1}{n+1} cdot i-(sum{i=1}^{n-1}C^{i+1}n cdot i) imes 2
& =sum{i=1}^{n}C^{i}_{n+1}
& =2^{n}-1
end{aligned}
end{equation}[ 故得：$F(n+1)=2F(n)+2^n-1$ 代码就不写了 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 预计得分：60 points ]已经写出递推公式的话有两种思路：1. 数学方法推通项公式；2. 矩阵快速幂加速递推公式。
-
方法一：数学方法推通项公式：
[egin{equation} egin{aligned} & F(n)=sum_{i=1}^{n-1}C_n^{i+1}cdot i\ & =sum_{i=1}^{n-1}{n!over(i+1)!(n-i-1)!}cdot i \ & =sum_{i=2}^n{n!over i!(n-i)!} cdot i+{n!over i!(n-i)!}\ & =sum_{i=2}^n{n!over(i-1)!(n-i)!}+C_n^i \ ]& ={sum_{i=2}^n{C_n^{i-1}}+(n-i+1)(2^n-n-1)over n-i+1}
& ={2^{n-1}-n-2+(n-i+1)(2^n-n-1)over n-i+1}
end{aligned}
end{equation}[ ]
-
这里 (2^{n-1}) 用快速幂实现（注意，不能用 (<<) 来做，会爆 long long）
代码见code1
时间复杂度：(O( ext{log}n))
空间复杂度：(O(1))
预计得分：100 points
-
方法二：矩阵快速幂优化：
个人认为这个方法可能鲜有人能想到（
太麻烦了），我就仔细讲一讲。首先，观察递推公式中有如下几个影响值：(F(n-1),2^{n-1},1) ,故与单位矩阵相乘的矩阵为
[egin{bmatrix} F(n-1)\ 2^{n-1}\ 1 end{bmatrix} ]得到的矩阵为
[egin{bmatrix} F(n)\ 2^{n}\ 1 end{bmatrix} ]有递推式显然可得：
[ egin{cases} F(n)=F(n-1) imes 2+2^{n-1} imes 1+1 imes(-1)\ 2^n=F(n-1) imes0+2^{n-1} imes 2+1 imes 0 \ 1=F(n-1) imes 0+2^{n-1} imes 0+1 imes 1 end{cases} ]（不会矩阵加速的可以做一做 P1939 【模板】矩阵加速（数列）和 P1962 斐波那契数列）
推出单位矩阵：
[egin{bmatrix} 2&1&-1\ 0&2&0\ 0&0&1 end{bmatrix} ]故矩阵递推式为：
[egin{bmatrix} F(n-1)\ 2^{n-1}\ 1 end{bmatrix} imes egin{bmatrix} 2&1&-1\ 0&2&0\ 0&0&1 end{bmatrix} = egin{bmatrix} F(n)\ 2^{n}\ 1 end{bmatrix} ]化为矩阵幂形式得：
[egin{bmatrix} F(2)\ 2^2\ 1 end{bmatrix} imes egin{bmatrix} 2&1&-1\ 0&2&0\ 0&0&1 end{bmatrix}^{n-2} = egin{bmatrix} F(n)\ 2^{n}\ 1 end{bmatrix} ]套魔板即可。
代码见code2
时间复杂度：(O( ext{log}n))
空间复杂度：(O(1))
两种方法的优劣：
- 第一种方法难算，需要较好的数学基础，但最后实现时时间复杂度在 (O(1)) — (O( ext{log}n)) ,常数极小。
- 第二种方法是数列加速的常用方法，简单易想，但常数较大，本题为常数为27，即在大数据下比第一种方法慢2—3倍
Code1:
#include<bits/stdc++.h>
//#define file
#define modn (int)(1e9+7)
#define int long long
using namespace std;
int n;
inline int ksm(int x,int y,int p)
{
if(y==0) return 1%p;
if(y==1) return x%p;
int rst=ksm(x,y/2,p)%p;
if(y%2==0)
{
return rst*rst%p;
}else
{
int tmp=rst*rst%p;
return tmp*x%p;
}
}
signed main()
{
#ifdef file
freopen("Agent1.in","r",stdin);
freopen("Agent1.out","w",stdout);
//F(n)=sum_{i=1}^{n-1}C^(i+1)_n*i
//F(n)=F(n-1)*2+2^{n-1}-1
#endif
scanf("%lld",&n);
int ans=(n-2)*ksm(2,n-1,modn)%modn+1;
printf("%lld
",ans);
return 0;
}
Code2(本代码为我的教练所写，码风可能有些许不同):
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int jz[3][3] = {{2,1,-1},{0,2,0},{0,0,1}},
jz1[3][3] = {{2,1,-1},{0,2,0},{0,0,1}};
int base[3][3];
void cheng()
{
memset(base,0,sizeof(base));
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
base[i][j] += jz1[i][k]*jz1[k][j];
base[i][j] = (base[i][j]+mod)%mod;
}
}
}
memcpy(jz1,base,sizeof(base));
}
void chengjz()
{
memset(base,0,sizeof(base));
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
base[i][j] += jz1[i][k]*jz[k][j];
base[i][j] = (base[i][j]+mod)%mod;
}
}
}
memcpy(jz1,base,sizeof(base));
}
void quickpow(int k)
{
if(k==1) return;
quickpow(k/2);
cheng();
if(k%2!=0) chengjz();
}
signed main()
{
int n;
cin>>n;
if(n==2)
{
printf("1");
return 0;
}
quickpow(n-2);
int ans = (jz1[0][0]+ 4*jz1[0][1]%mod + mod + 1*jz1[0][2]) mod;
cout<<ans;
return 0;
}