)
以弱胜强的秘密京东技术岗 8月8号笔试 第二题题目内容在一场单败淘汰赛中共有N2mN 2^mN2m名选手参加。他们的能力值恰好是111到NNN的每一个整数没有重复。比赛采用固定的淘汰规则首先将所有选手按照某种初始顺序排成一行。每一轮将当前序列中相邻的两人配对对战第111名对第222名第333名对第444名以此类推。若能力值为xxx的选手与能力值为yyy的选手对战则xxx获胜的概率为xxy\frac{x}{xy}xyx。每轮结束后胜者保持原有相对顺序形成新的序列继续下一轮直至产生唯一的冠军。现在你希望能力值为111的选手获得最终冠军的概率尽可能大。请问在所有可能的初始排列中有多少种排列方式可以使得能力值为111的选手的夺冠概率达到最大值答案请对998244353998244353998244353取模。数据范围mmm满足1≤m≤121 \le m \le 121≤m≤12。输入描述输入包含一行一个整数mmm1≤m≤121 \le m \le 121≤m≤12表示选手总数为2m2^m2m。输出描述输出一行一个整数表示满足条件的初始排列数量对998244353998244353998244353取模后的结果。样例1输入1输出2说明当m1m1m1时总选手数N212N2^12N212能力值为1和2。无论怎样排列能力值为1的选手夺冠概率均为11213\frac{1}{12}\frac{1}{3}12131即所有2!22! 22!2种排列都能使夺冠概率达到最大值。因此答案为2。样例2输入3输出128说明总选手数N238N2^38N238。要使能力值为1的选手夺冠概率最大必须使其在每一轮中对阵的对手尽可能弱。可以证明满足条件的初始排列总数为2N−1271282^{N-1}2^71282N−127128。对998244353998244353998244353取模后仍为128。样例3输入4输出32768说明总选手数N2416N2^416N2416。同理最优排列数量为2N−1215327682^{N-1}2^{15}327682N−121532768取模后结果为32768。思路解题思路:数学原理 逻辑分析最佳答案就为2^(N - 1) 其中N 2^m,然后对 998244353取模即可。为了让1最终获胜概率最大较强的选手尽量在1到达它们之前相互比赛。以m3为例子期待的比较方式为冠军 ● / \ ● ● / \ / \ ● ● ● ● / \ / \/ \ / \ 1 2 3 4 5 6 7 8可以很容易看出比较过程为完全二叉树并且二叉树的叶子节点数量为N, 对于完全二叉树内部节点数量为N-1, 并且每个内部节点左节点和右节点可以交换顺序不影响最终结果那么方案数就为2^(N-1)求2^(N-1)可使用快速幂算法。C#includebits/stdc.husingnamespacestd;usinglllonglong;constll MOD998244353;llqpow(ll a,ll b){ll res1;while(b){if(b1)resres*a%MOD;aa*a%MOD;b1;}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intm;cinm;intN1m;// 最优排列对应一棵完全二叉树// 每个内部节点的左右子树可以交换// N 个叶子共有 N-1 个内部节点// 因此答案为 2^(N-1)coutqpow(2,N-1)\n;return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{staticfinallongMOD998244353L;staticlongqpow(longa,longb){longres1;while(b0){if((b1)!0){resres*a%MOD;}aa*a%MOD;b1;}returnres;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intmInteger.parseInt(br.readLine().trim());intN1m;// 最优排列对应一棵完全二叉树// 每个内部节点的左右子树可以交换// N 个叶子共有 N-1 个内部节点// 因此答案为 2^(N-1)System.out.println(qpow(2,N-1));}}pythonimportsys MOD998244353defqpow(a,b):res1whileb:ifb1:resres*a%MOD aa*a%MOD b1returnres mint(input())N1m# 最优排列对应一棵完全二叉树# 每个内部节点的左右子树可以交换# N 个叶子共有 N-1 个内部节点# 因此答案为 2^(N-1)print(qpow(2,N-1))javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constMOD998244353n;functionqpow(a,b){letres1n;while(b0){if(b1){resres*a%MOD;}aa*a%MOD;bMath.floor(b/2);}returnres;}rl.on(line,(line){constmNumber(line.trim());constN1m;// 最优排列对应一棵完全二叉树// 每个内部节点的左右子树可以交换// N 个叶子共有 N-1 个内部节点// 因此答案为 2^(N-1)console.log(qpow(2n,N-1).toString());rl.close();});Gopackagemainimport(bufiofmtos)constMODint64998244353funcqpow(a,bint64)int64{varresint641forb0{ifb1!0{resres*a%MOD}aa*a%MOD b1}returnres}funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varmintfmt.Fscan(in,m)N:1m// 最优排列对应一棵完全二叉树// 每个内部节点的左右子树可以交换// N 个叶子共有 N-1 个内部节点// 因此答案为 2^(N-1)fmt.Fprintln(out,qpow(2,int64(N-1)))}
