核心内容摘要
【拉着我的手，丈量世界】1-3岁幼儿“大马拉小车”的奇妙探索之旅
小红的好排列时间限制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^
(
取模后输出。
长度为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^
n(2≦n≦
代表排列中的元素数量。
输出描述输出一个整数代表好排列的数量。
由于答案可能很大请将答案对( 10 9 7 ) (10^
(
取模后输出。
示例1输入2输出0说明在这个样例中长度为2 22的排列有且仅有两个{ 1 , 2 } \{ 1,2 \}{1,2}第一个元素1 11使得1 × 1 1 1×111×11第二个元素2 22使得2 × 2 4 2×242×24均不是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×111×11第二个元素2 22使得2 × 2 4 2×242×24第三个元素4 44使得4 × 3 12 4×3124×312第四个元素3 33使得3 × 4 12 3×4123×412恰好有一半的i ii使得a i × i a_i×iai×i是3 33的倍数。
解题思路首先预处理阶乘和逆元阶乘借助费马小定理快速幂求逆元用于O ( 1 ) O(
O(
计算组合数统计1 ˜ n 1 \~\ n1˜n中3 33的倍数的数及位置个数k n / / 3 kn//3kn//3非3 33的倍数的数及位置个数m n − k mn−kmn−k。
好排列要求恰好n / 2 n/2n/2个位置满足a i × i a_i×iai×i是3 33的倍数推导得该条件等价于选择x n / 2 − k xn/2−kxn/2−k个“非3 33倍数位置”放3倍数数、同时选x xx个“3 33倍数位置”放非3 33倍数数x 0 x0x0则无合法解。
计算组合数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 1e971e97取模。
预处理阶乘的时间复杂度O ( n ) O(n)O(n)组合数计算O ( 1 ) O(
O(
适配n ≤ 1 e 6 n≤1e6n≤1e6的规模精准统计好排列的数量。
代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N1e610;ll f[N],inf[N];llqp(ll a,ll b){ll res1;while(b){if(b