(nowcoder22529c) diner (inclusion exclusion principle + permutation and combination)

Topic link ： Sign in — major IT Written interview preparation platform _ Cattle from

subject ：

The sample input ：

1000000

Sample output ：

270258012

analysis ： set up Ai It means the first one i Yes cp The property of adjacency , Then we are asking for N((1-A1)(1-A2)……(1-An)), Show first i Yes cp Adjacent number , because n Yes cp There is no distinction , So we can choose any i Yes cp Indicates that it is adjacent , The number of selected schemes is C(n,i), Each pair cp Next to each other, we regard them as a point , So the total is n*2-i A little bit , Because it is arranged in a ring , Then we need to take any point as the head node , The rest of the points can be fully arranged , Then the number of permutation schemes is (n-2*i-1)!, Each pair cp The internal arrangement is arbitrary , So there are two situations , All in all i Yes cp, So contribution is 2^i, Then apply the formula of the principle of inclusion and exclusion to get ：

This question has strict requirements for time and space , So we must optimize as much as possible , I attach the non optimized code and the optimized code for you to compare

Unoptimized code （ Overtime ）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N=6e7+10,mod=1e9+7;
ll fac[N],inv[N];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
ll C(ll a,ll b)
{
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
	ll n;
	cin>>n;
	if(n==1)
	{
		puts("0");
		return 0;
	}
	fac[0]=inv[0]=1;
	for(int i=1;i<=2*n;i++)
		fac[i]=fac[i-1]*i%mod;
	inv[2*n]=qpow(fac[2*n],mod-2);
	for(int i=2*n-1;i>=1;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	ll ans=0;
	int sign=1;
	for(int i=0;i<=n;i++)
	{
		ans=(ans+sign*C(n,i)*fac[2*n-i-1]%mod*qpow(2,i))%mod;
		ans=(ans+mod)%mod;
		sign=-sign;
	}
	printf("%lld",ans);
	return 0;
}

Optimized code ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int N=3e7+10,mod=1e9+7;
int inv[N];
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int main()
{
	ll n;
	cin>>n;
	if(n==1)
	{
		puts("0");
		return 0;
	}
	inv[0]=1;
	for(int i=1;i<=n;i++)
		inv[i]=1ll*inv[i-1]*i%mod;
	inv[n]=qpow(inv[n],mod-2);
	for(int i=n-1;i>=1;i--)
		inv[i]=1ll*inv[i+1]*(i+1)%mod;
	ll ans=0;
	ll sign;
	ll fac1=1,fac2=1,p2=1;
	ll inv2=qpow(2,mod-2);//inv2 Record 2 About mod Inverse element  
	//fac1 Record fac[n],fact2 Record fac[2*n-i-1],p2 Record qpow(2,i) 
	for(int i=1;i<=n;i++) fac1=fac1*i%mod,p2=p2*2%mod;
	for(int i=1;i<n;i++) fac2=fac2*i%mod;
	if(n&1) sign=-1;
	else sign=1;
	for(int i=n;i>=0;i--)
	{
//		ans=(ans+sign*C(n,i)*fac[2*n-i-1]%mod*qpow(2,i))%mod;
		ans=(ans+sign*fac1*inv[i]%mod*inv[n-i]%mod*fac2%mod*p2)%mod;
		fac2=fac2*(2*n-i)%mod;
		p2=p2*inv2%mod; 
		sign=-sign;
	}
	ans=(ans%mod+mod)%mod;
	printf("%lld",ans);
	return 0;
}