小红的好排列【牛客tracker 每日一题】

小红的好排列

时间限制：1秒 空间限制：256M

知识点：数论

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红认为一个偶数长度为n nn的排列{ a 1 , a 2 , … , a n } \{ a_1,a_2,…,a_n \}{a1​,a2​,…,an​}是好排列，当且仅当恰好有一半的i ii使得a i × i a_i×iai​×i是3 33的倍数。
小红想知道，全部长度为n nn的排列中，共有多少个好排列？由于答案可能很大，请将答案对( 10 9 + 7 ) (10^9+7)(109+7)取模后输出。

长度为n nn的排列是由1 ∼ n 1∼n1∼n这n nn个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{ 2 , 3 , 1 , 5 , 4 } \{ 2,3,1,5,4 \}{2,3,1,5,4}是一个长度为5 55的排列，而{ 1 , 2 , 2 } \{ 1,2,2 \}{1,2,2}和{ 1 , 3 , 4 } \{ 1,3,4 \}{1,3,4}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述：

在一行上输入一个正偶数n ( 2 ≦ n ≦ 10 6 ) n(2≦n≦10^6)n(2≦n≦106)代表排列中的元素数量。

输出描述：

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对( 10 9 + 7 ) (10^9+7)(109+7)取模后输出。

示例1

输入：

2

输出：

0

说明：

在这个样例中，长度为2 22的排列有且仅有两个：

• { 1 , 2 } \{ 1,2 \}{1,2}，第一个元素1 11使得1 × 1 = 1 1×1=11×1=1，第二个元素2 22使得2 × 2 = 4 2×2=42×2=4，均不是3 33的倍数；
• { 2 , 1 } \{ 2,1 \}{2,1}，同理。
  因此，长度为2 22的排列中，不存在好排列。

示例2

输入：

4

输出：

18

说明：

在这个样例中，一共有18 1818个长度为4 44的排列满足条件，例如：

• { 1 , 2 , 4 , 3 } \{ 1,2,4,3 \}{1,2,4,3}，第一个元素1 11使得1 × 1 = 1 1×1=11×1=1，第二个元素2 22使得2 × 2 = 4 2×2=42×2=4，第三个元素4 44使得4 × 3 = 12 4×3=124×3=12，第四个元素3 33使得3 × 4 = 12 3×4=123×4=12，恰好有一半的i ii使得a i × i a_i×iai​×i是3 33的倍数。

解题思路

首先预处理阶乘和逆元阶乘（借助费马小定理快速幂求逆元），用于O ( 1 ) O(1)O(1)计算组合数；统计1 ˜ n 1 \~\ n1˜n中3 33的倍数的数（及位置）个数k = n / / 3 k=n//3k=n//3，非3 33的倍数的数（及位置）个数m = n − k m=n−km=n−k。好排列要求恰好n / 2 n/2n/2个位置满足a i × i a_i×iai​×i是3 33的倍数，推导得该条件等价于选择x = n / 2 − k x=n/2−kx=n/2−k个“非3 33倍数位置”放3倍数数、同时选x xx个“3 33倍数位置”放非3 33倍数数（x < 0 x<0x<0则无合法解）。计算组合数C ( m , x ) × C ( k , x ) C(m,x)×C(k,x)C(m,x)×C(k,x)，再乘以3 33倍数数的全排列f [ k ] f[k]f[k]、非3 33倍数数的全排列f [ m ] f[m]f[m]，结果对1 e 9 + 7 1e9+71e9+7取模。预处理阶乘的时间复杂度O ( n ) O(n)O(n)，组合数计算O ( 1 ) O(1)O(1)，适配n ≤ 1 e 6 n≤1e6n≤1e6的规模，精准统计好排列的数量。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;ll f[N],inf[N];llqp(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}returnres;}voidinit(){f[0]=1;for(ll i=1;i<N;i++)f[i]=f[i-1]*i%p;inf[N-1]=qp(f[N-1],p-2);for(ll i=N-2;i>=0;i--)inf[i]=inf[i+1]*(i+1)%p;}llC(ll n,ll k){if(k<0||k>n)return0;returnf[n]*inf[k]%p*inf[n-k]%p;}intmain(){init();ll n;if(cin>>n){ll k=n/3;ll x=n/2-k;if(x<0){cout<<0<<endl;return0;}ll ans=C(n-k,x);ans=ans*C(k,x)%p;ans=ans*f[k]%p;ans=ans*f[n-k]%p;cout<<ans<<endl;}return0;}