抱歉，这没有集美

NC245517. 抱歉，这没有集美

描述

众所周知，集美大学的新生开学仪式（并不）是这样的：

今年预计招收 $n$ 名新生，将他们依次按照 $1\sim n$ 编号。
拿来 $n$ 个球，也是按照 $1\sim n$ 编号，然后将其打乱后发放给新生，第 $i$ 位新生分到的球编号为 $p_i$ 。
若对于某个一个编号为 $i$ 的新生， $gcd(p_i,i)$ 为偶数，则被认定为天选之子，他将会变身为集美。其中 $\text{gcd}(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

Tenshi是集美大学 $2023$ 年的新生，他酷爱女装，所以他一直梦想变成集美。因为出于对新生隐私的保护，贝贝并不知道Tenshi的编号，他想先计算下有多少种发球方案能让Tenshi变身为集美的概率不为 $0$ （即一个方案至少存在一个位置能变身集美，则概率就不为 $0$ ）。

输入描述

仅一行，包含一个整数，表示新生的数量。

输出描述

输出一行，包含一个整数，如题意所示，答案取模。

示例1

输入:

输出:

说明:

$20$ 种方案依次为：

1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
2, 1, 3, 4
2, 3, 1, 4
2, 4, 1, 3
2, 4, 3, 1
3, 1, 2, 4
3, 1, 4, 2
3, 2, 1, 4
3, 2, 4, 1
3, 4, 1, 2
3, 4, 2, 1
4, 1, 3, 2
4, 2, 1, 3
4, 2, 3, 1
4, 3, 1, 2

示例2

输入:

输出:

731904262

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

C++(g++ 7.5.0) 解法, 执行用时: 22ms, 内存消耗: 7412K, 提交时间: 2022-11-05 13:24:46

#include <bits/stdc++.h>
using namespace std;
long long n, a[1<<20] = {1}, mod = 1e9 + 7;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		a[i] = a[i-1] * i % mod;
	cout << ((a[n] - a[n+1>>1] * a[n+1>>1] % mod) + mod) % mod;
}

C++(clang++ 11.0.1) 解法, 执行用时: 22ms, 内存消耗: 7376K, 提交时间: 2022-12-06 11:05:19

#include<bits/stdc++.h>
using namespace std;
long long n,a[1<<20]={1},mod=1e9+7;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	a[i]=a[i-1]*i%mod;
	cout<<((a[n]-a[n+1>>1]*a[n+1>>1]%mod)+mod)%mod;
}

Python3 解法, 执行用时: 402ms, 内存消耗: 4648K, 提交时间: 2022-11-15 16:05:12

p=int(1e9+7)
n=int(input())
a=b=1
for i in range(1,(n+3)//2): a=a*i%p 
for i in range(1,n+1): b=b*i%p 
print((b-a*a)%p)