题解
- 先给大家送上一句话：水法真神奇，暴力出奇迹！！！
- 大爷说这题可以打表找规律！！！大爷说这题可以打表找规律！！！大爷说这题可以打表找规律！！！
- 重要的事请说三遍
- 规律：f[i]=(f[i-1]+f[i-2])*(i-1)+f[i-3]
- 以上是水法时间
- 正解要来啦：
- 对于这题，我们可以反向思维求错误的方案数
- 容斥原理，假设有 1 堂课所在的天数是错误的情况数是 W(1)
- 则每个错误的课程 i 可以放在 i 或 i+1 天，剩下的选课方法数是(n-1)!
- 所以 w(1)=C(n,1)*2*(n-1)!
- 那么对于 2 个以上的情况，假设有 k 堂课所在的天数是错误的情况数是 W(K)
- 总共 n 堂课分别 记为 1,2,...n,它们可放的天数可以表示为(1，2)(2，3)(3，4)...(n，1)
- 现在我们把括号去掉即得到一个数列 1，2，2，3，3，4，....n，1，
- 现在 我们从里面取出 K 个数，分别表示 k 堂课所在的天数
- 现在只要求出满足 这个条件的取法数就可以了
- 定理：假定数n个顶点沿一圆周排列，则从其中选取k个不相邻顶点的方法 数是n/k*C(n-k-1,k-1)
- 证明：对于任意一个顶点A，先取A，然后再从不和A相邻的n-3个其他顶点 中取k-1个不相邻顶点
- 显然可得到符合定理要求的组合，这个组合的个数 为C((n-3)-(k-1)+1,k-1)=C(n-k-1,k-1)
- 一共有n个顶点，而且在每个组 合中有k个元素，即可完成证明
- 那么W(K)=(n-k)!*C(2n-k-1,k-1)*2n/k
- 有人会问为什么要乘(n-k)!，因为我们只选了K堂错的课，剩余(n-k) 堂课可以随意选
- W(K)确定以后就是最裸的容斥原理了
正解代码
1 #include <cstdio>
2 #include <iostream>
3 using namespace std;
4 const int mo=1000000007,maxn=200005;
5 int n;
6 long long f[maxn],ny[maxn];
7 long long ksm(long long k,int t)
8 {
9 if (!t) return 1;
10 long long mid=ksm(k,t/2);
11 if (t&1) return mid*mid%mo*k%mo;
12 return mid*mid%mo;
13 }
14 long long get(int x) { return f[n-x]%mo*2*n%mo*(f[2*n-x-1]*(ny[x]*ny[2*(n-x)]%mo)%mo)%mo; }
15 int main()
16 {
17 f[0]=f[1]=1; ny[0]=ny[1]=1;
18 for (int i=2;i<maxn;i++) f[i]=f[i-1]*i%mo,ny[i]=ksm(f[i],mo-2);
19 while (scanf("%d",&n)!=EOF)
20 {
21 if (n==1) { printf("0
"); continue; }
22 long long ans=f[n];
23 for (int i=1;i<=n;i++)
24 {
25 long long k=get(i);
26 if (i%2==1) ans=(ans-k+mo)%mo; else ans=(ans+k)%mo;
27 }
28 printf("%lld
",ans);
29 }
30 return 0;
31 }
水法代码
1 #include<cstdio>
2 using namespace std;
3 int n;long long f[100001];
4 int main()
5 {
6 f[3]=1,f[4]=3;
7 for (int i=5;i<=100000;i++) f[i]=((f[i-1]+f[i-2])*(i-1)+f[i-3])%1000000007;
8 while (scanf("%d",&n)!=EOF) printf("%lld
",(f[n]-f[n-1]+1000000007)%1000000007);
9 }