JZOJ-senior-5878. 【NOIP2018提高组模拟9.22】电路图 A
Time Limits: 1000 ms Memory Limits: 262144 KB
Description
nodgd 要画一个电路图。
这是一个很简单的电路图,所有的元件都是串联关系,从整体来看就是一个环状的结构。画电路图有很多要求,nodgd 为了画得好看就又添加了一些
额外的要求。所有要求归结起来有以下几点:
1、这个环状电路上有n个双端电路元件(即每个电路元件有两个连接导线的接头),其中只有一个直流电源;为了本题方便,其他n − 1个元件都是一模一样的电阻。
2、电流在电路图中每经过一个元件,就必须拐一个90°的弯;没有经过元件时不允许拐弯。参考下图。
3、从电路图整体上观察,电流沿顺时针方向流动,且电路不能自交。参考下图。
4、如果一个符合题意的电路图,可以通过整体旋转一定的角度,再适当调整图中导线的长度,得到另外一个符合题意的电路图,则这两个电路图是相同的。参考下图。
5、如果电路环路的内部存在一个点,使得它可以“看到”电路环路内部的所有位置,就认为这个图是美观的,反之是不美观的。相同的电路图不一定都美观。参考下图。
那么问题来了,nodgd 想知道有多少种不同的电路图,以及有多少种不同的美观电路图。由于两个问题的答案都可能很大,请mod 1,000,000,007输出结果。
Input
输入文件 A.in
输入文件第一行包含一个正整数n,表示包含电源在内的电路元件的总数量。
Output
输出文件 A.out。
输出文件第一行包含一个整数,表示不同的电路图数量mod 1,000,000,007的结果。第二行包含一个整数,表示不同的美观电路图数量mod 1,000,000,007的结果。
Sample Input
【样例1】
6
【样例2&3】见下发文件
Sample Output
【样例1】
6
6
Data Constraint
对于 10%的数据,n = 12;
对于 30%的数据,n ≤ 24;
对于 60%的数据,n ≤ 5000;
对于 100%的数据,4 ≤ n ≤ 10^7,且n是个偶数。
Hint
【输入输出样例 1 说明】
可以有如下几种电路图,电路图数量是 6,所以输出文件第一行输出一个整数 6; 容易发现,这 6 个电路图都是美观的电路图,所以第二行也输出一个整数 6。
Solution
看这很不友善的 ,就知道是个结论题啦
第一问:
题目中说每经过一个元件就必须拐一次弯,而由于电路图是闭合的
不难发现右拐次数一定为左拐次数+4
所以 就是
第二问:
题目中要求的美观实际上就是要求形成的电路图为凸多边形
观察可知,不能连续两次逆时针拐弯,否则就不美观了
于是我们以最外围的四条边为分界,将路径分成四段,手动画一画可以发现每段的拐弯数均为奇数
(最外围的四条边顾名思义就是最上最下最左和最右四条边,最左边的边就是以那条边为分界,所有边都在它的右半边,其他三条边同理)
那么问题转化为将一个偶数 拆分成 个奇数的方案数
我们先考虑将 拆成 4 个偶数怎么做
将 个偶数排在一起形成一个序列,保证了每个偶数>0且<N
在它们之中选 个出来,这 个数相当于挡板,将序列分成了四个部分
假定选出来的 个数分别为 ,然后我们将间隔作为选择的偶数
那么这四个正偶数分别为
于是我们就可以得出方案数为
回到这题,要将 分成 个正奇数
分成奇数,就相当于分成偶数后将每个偶数-1
于是我们类比上面的做法
我们将这四个奇数分别都加上1 ,则和为
于是方案数为 ,即
由于电源放任意位置都可以,所以要乘上
又因为整体旋转后相同的电路图都是一样的,所以还要除以4
最终,
Code
#include<algorithm>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=1e7+5,P=1e9+7;
int n,jc[N],ny[N];
int ksm(int x,int y)
{
int s=1;
for(;y;x=(ll)x*x%P,y>>=1)
if(y&1) s=(ll)s*x%P;
return s;
}
ll C(int n,int m)
{
return (ll)jc[n]*(ll)ny[m]%P*(ll)ny[n-m]%P;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
jc[0]=1;
fo(i,1,n) jc[i]=(ll)jc[i-1]*i%P;
ny[n]=ksm(jc[n],P-2);
fd(i,n-1,0) ny[i]=(ll)ny[i+1]*(i+1)%P;
ll a1=C(n,n/2-2);
ll a2=C(n/2+1,3)*n%P*ksm(4,P-2)%P;
printf("%lld\n%lld",a1,a2);
}