最后的晚餐(dinner)

NC19857. 最后的晚餐(dinner)

描述

**YZ（已被和谐）的食堂实在是太挤辣！所以Apojacsleam现在想邀请他的一些好友去校外吃一顿饭，并在某酒店包下了一桌饭。

当Apojacsleam和他的同学们来到酒店之后，他才发现了这些同学们其实是N对cp，由于要保护广大单身狗的弱小心灵（FF！），所以他不想让任意一对情侣相邻。

说明：

·酒店的桌子是恰好有2N个位置的圆桌。

·客人恰好是N对cp，也就是说，圆桌上没有空位。

·桌子的每一个位置是一样的，也就是说，如果两种方案可以通过旋转得到，那么这就可以视为相等的。

现在，你需要求出，将任意一对情侣不相邻的方案数。

·

输入描述

一行一个正整数N，表示cp的对数。

输出描述

一行一个非负整数，表示答案对1000000007取模后的值。

示例1

输入:

输出:

说明:

两种方案：

假设1-2、3-4是两对情侣。

方案有1-3-2-4

1-4-2-3

或者你也可以认为1-3-2-4

2-3-1-4

是合法的方案。

示例2

输入:

输出:

535659175

示例3

输入:

输出:

270258012

说明:

对于20%的数据，1<=N<=5
对于30%的数据，1<=N<=20
对于50%的数据，1<=N<=100
对于70%的数据，1<=N<=200000
对于100%的数据，1<=N<=30000000

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 461ms, 内存消耗: 416K, 提交时间: 2019-11-14 18:55:51

#include<cstdio>
typedef long long ll;
const int mod=1e9+7;
int n;
ll ans=1,a,b,c;
int main()
{
    scanf("%d",&n);
    if(n==1){puts("0");return 0;}
    a=1;b=n-2;
    for(int i=2;i<=n;i++)
        c=(b*(ll)(n+i-3)+a*(ll)(i-1<<1))%mod,a=b,b=c;
    for(int i=2;i<n;i++)
        ans=ans*(ll)i%mod;
    ans=ans*c%mod;
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 448ms, 内存消耗: 592K, 提交时间: 2018-10-29 00:13:23

#include<bits/stdc++.h>
const int mod=1e9+7;
int n;long long a,b,c,ans=1;
int main()
{
    scanf("%d",&n);
    if(n==1){puts("0");return 0;}
    a=1;b=n-2;
    for(int i=2;i<=n;i++)c=(1ll*b*(n+i-3)+2ll*a*(i-1))%mod,a=b,b=c;
    for(int i=2;i<n;i++)ans=1ll*ans*i%mod;
    printf("%lld\n",1ll*ans*c%mod);
    return 0;
}