题目大意

  有 $n$n 个人玩淘汰赛。
  每一轮，假设当前还剩 $k$k 人，则他们随机分成 $\lfloor \frac k2 \rfloor$⌊2k​⌋ 组（$k$k 为奇数时有一人轮空），最后晋级 $\lceil \frac k2 \rceil$⌈2k​⌉ 人。每个人能力互不相同，两人对打时一定是能力强者获胜。
  求所有可能的局面数，答案对 $2^{64}$264 取模。

  $1 \leq n \leq 10^{18}$1≤n≤1018

  注意题面坑：Two tournaments are called different if there is a game (between two participants) in one of the tournaments that doesn’t occur in the other tournament. 这句话是错的！

$\\$
$\\$
$\\$

题解

  这题的难点在于揣摩出题人的正确题意
  题意演我 3 个小时出题人今晚买菜必涨价

  考虑递推。设 $f(n)$f(n) 为 $n$n 个人时的方案数。
  当 $n$n 为奇数时，设 $m=\lfloor \frac n2 \rfloor$m=⌊2n​⌋，轮空一个人有 $n$n 种情况，分组有 $\frac{(2m)!}{2^m m!}$2mm!(2m)!​ 种情况（给 $2m$2m 个人标号 $1$1~$2m$2m，$i$i 和 $m+i$m+i 一组，然后去重），晋级的 $m+1$m+1 个人打接下来的比赛有 $f(m+1)$f(m+1) 种情况，故
$f(n)=n\cdot \frac{(2m)!}{2^m m!} \cdot f(m+1)=n!!\cdot f(\lceil \frac n2 \rceil)$f(n)=n⋅2mm!(2m)!​⋅f(m+1)=n!!⋅f(⌈2n​⌉)

  偶数同理，得到
$f(n)=\frac{(2m)!}{2^m m!} \cdot f(m)=(n-1)!!\cdot f(\frac n2)$f(n)=2mm!(2m)!​⋅f(m)=(n−1)!!⋅f(2n​)
  如何求 $n!!~\text{mod}~2^{64}$n!! mod 264 呢？这个技巧还是不错的。
  首先这个 $n$n 是个奇数，设 $P_k(x)=\prod_{i=1}^k(2x+2i-1)=(2x+1)(2x+3)\cdots(2x+2k-1)$Pk​(x)=∏i=1k​(2x+2i−1)=(2x+1)(2x+3)⋯(2x+2k−1)，而这个 $P_k(0)$Pk​(0) 就是要求的值。
  $P_k(x)$Pk​(x) 是关于 $x$x 的多项式，而这个多项式对于 $x^{64}$x64 及以上的项，系数都含有 $2^{64}$264，模意义下为 $0$0，因此这个多项式只用考虑前 64 项（$x^0$x0 至 $x^{63}$x63）。因此这个多项式的普通乘法是 $O(64\cdot 64)$O(64⋅64) 的。
  考虑倍增求这个多项式，假设已知 $P_k(x)$Pk​(x)，那么 $P_{2k}(x)=P_k(x)P_k(x+k)$P2k​(x)=Pk​(x)Pk​(x+k)，具体实现就先用 $O(64\cdot 64)$O(64⋅64) 的时间求出 $P_k(x+k)$Pk​(x+k)，然后再用 $O(64\cdot 64)$O(64⋅64) 的乘法求出 $P_{2k}(x)$P2k​(x)。通过 $P_{2k}(x)$P2k​(x) 求 $P_{2k+1}(x)$P2k+1​(x) 同理。

题面的题意

  如果按照题面的题意要怎么做呢？

  其实差别就是，比如 $n=3$n=3 的时候，3 先跟 1 打再跟 2 打，与 3 先跟 2 打再跟 1 打是等价的。
  我们给要对打的两个人连边，它形成了一棵树，所以不同的局面数就是合法的生成树的个数。
  有标号生成树计数，考虑 prufer 序。

  然后不会了

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int maxw=130;

struct P{
	ULL a[maxw];
	LL k;
} zero,re;

LL n;

ULL C[70][70];
void C_Pre(int n)
{
	fo(i,0,n)
	{
		C[i][0]=1;
		fo(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
}

P mul1(const P &x,P y)
{
	fo(i,0,63)
	{
		ULL kpow=x.k;
		for(int j=i-1; j>=0; j--, kpow*=x.k) y.a[j]+=C[i][i-j]*kpow*y.a[i];
	}
	re.k=x.k+y.k;
	fo(i,0,63) re.a[i]=0;
	fo(i,0,63)
		fo(j,0,63) re.a[i+j]+=x.a[i]*y.a[j];
	return re;
}
P mul2(const P &x,const P &y)
{
	fo(i,0,63) re.a[i]=0;
	fo(i,0,63)
		fo(j,0,63) re.a[i+j]+=x.a[i]*y.a[j];
	return re;
}

P fac(LL n)
{
	P re=zero, x=zero;
	re.a[0]=1, x.k=1, x.a[0]=1, x.a[1]=2;
	for(n=(n+1)>>1; n; n>>=1, x=mul1(x,x)) if (n&1) re=mul1(re,x);
	return re;
}

P dfs(LL n)
{
	if (n<=2)
	{
		re=zero;
		re.a[0]=1;
		return re;
	}
	return (n&1) ?mul2(dfs(n-(n>>1)),fac(n)) :mul2(dfs(n>>1),fac(n-1)) ;
}

int main()
{
	C_Pre(65);
	
	scanf("%lld",&n);
	
	P ans=dfs(n);
	printf("%llu\n",ans.a[0]);
}