题意

求

16

16

16 进制下，

n

!

n!

n! 去掉尾部

0

0

0 后取模

2

64

2^{64}

264 的结果。

n

<

2

64

n<2^{64}

n<264

一共

T

≤

10

T\leq10

T≤10 组数据。

题解

存在一个末尾的

0

0

0 ，意味着能被

2

4

2^4

24 整除。我们就把这个数含有的

2

2

2 的次数求出来，取模

4

4

4 ，再乘上去。我们可以用扩展Lucas类似的方法，把目标不断除以 2 来统计，即依次统计能被

2

1

,

2

2

,

2

3

,

.

.

.

,

2

63

2^1,2^2,2^3,...,2^{63}

21,22,23,...,263 整除的数的个数，再加起来。剔除所有的

2

2

2 后，答案变成了

∏

i

=

0

f

(

n

2

i

)

\prod_{i=0} f(\frac{n}{2^i})

i=0∏​f(2in​)

其中

f

(

n

)

=

∏

i

=

1

(

n

+

1

)

/

2

−

1

(

2

i

+

1

)

f(n)=\prod_{i=1}^{(n+1)/2-1}(2i+1)

f(n)=∏i=1(n+1)/2−1​(2i+1) 。

现在我们的问题变成了求

f

(

n

)

f(n)

f(n) ，我们把它展开，

喔
 

唷

，
 

崩
 

溃
 

啦

_{喔\,唷，\,崩\,溃\,啦}

喔唷，崩溃啦​

这里的

n

n

n 太大了，看来我们得换个思路，我们令

2

=

x

2=x

2=x ，在取模

2

64

2^{64}

264 下，我们会发现只存在

x

x

x 的

1

∼

63

1\sim63

1∼63 次项。我们再展开：

∑

i

=

0

63

g

(

n

+

1

2

−

1

,

i

)

⋅

x

i

\sum_{i=0}^{63} g(\frac{n+1}{2}-1,i)\cdot x^i

i=0∑63​g(2n+1​−1,i)⋅xi

这里的

g

(

n

,

m

)

g(n,m)

g(n,m) 表示从

1

∼

n

1\sim n

1∼n 中选

m

m

m 个数相乘的所有方案之和。

未曾设想的方向：

g

(

n

,

m

)

g(n,m)

g(n,m) 是可以递推的，不难得出递推式为

g

(

n

,

m

)

=

g

(

n

−

1

,

m

)

+

g

(

n

−

1

,

m

−

1

)

×

n

g(n,m)=g(n-1,m)+g(n-1,m-1)\times n

g(n,m)=g(n−1,m)+g(n−1,m−1)×n

这个式子看起来有点熟悉，我们想想另一个递推式：

s

(

n

,

m

)

=

s

(

n

−

1

,

m

−

1

)

+

s

(

n

−

1

,

m

)

×

(

n

−

1

)

s(n,m)=s(n-1,m-1)+s(n-1,m)\times(n-1)

s(n,m)=s(n−1,m−1)+s(n−1,m)×(n−1)

所以不难发现第一类斯特林数

s

(

n

,

m

)

s(n,m)

s(n,m) 和

g

(

n

,

m

)

g(n,m)

g(n,m) 之间的关系：

g

(

n

,

m

)

=

s

(

n

+

1

,

n

−

m

+

1

)

g(n,m)=s(n+1,n-m+1)

g(n,m)=s(n+1,n−m+1)

太好啦，我们可以直接计算第一类斯特林数：

喔
 

唷

，
 

崩
 

溃
 

啦

_{喔\,唷，\,崩\,溃\,啦}

喔唷，崩溃啦​

还是不行，因为这里的

n

+

1

n+1

n+1 太大了，

m

m

m 虽然很小，但是

n

−

m

+

1

n-m+1

n−m+1 太大了。

考虑到第一类斯特林数的定义是若干个数组成圆排列，我们可以利用

m

m

m ，因为大小超过

1

1

1 的圆排列个数小于等于

m

m

m 。所以：

s

(

n

+

1

,

n

−

m

+

1

)

=

∑

i

=

0

m

d

p

[

m

]

[

i

]

⋅

(

n

+

1

m

+

i

)

s(n+1,n-m+1)=\sum_{i=0}^{m} dp[m][i]\cdot{n+1\choose m+i}

s(n+1,n−m+1)=i=0∑m​dp[m][i]⋅(m+in+1​)

其中

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 表示

i

+

j

i+j

i+j 个数形成

j

j

j 个大小不为

1

1

1 的圆排列的方案数，

这个也是可以递推的，讨论最末尾一个圆排列大小是否大于

2

2

2 ，可得递推式

d

p

[

i

]

[

j

]

=

(

d

p

[

i

−

1

]

[

j

]

+

d

p

[

i

−

1

]

[

j

−

1

]

)

×

(

i

+

j

−

1

)

dp[i][j]=\big(dp[i-1][j] + dp[i-1][j-1]\big)\times\big(i+j-1\big)

dp[i][j]=(dp[i−1][j]+dp[i−1][j−1])×(i+j−1)

---

组合数的计算是个难题，因为要用除法，但是

2

64

2^{64}

264 又不是个很好的模数。

所以，我们要把分子和分母的所有

2

2

2 都提出来，然后相除，再放到组合数里。

---

综合算下来，时间复杂度

O

(

T

log

⁡

4

n

)

O(T\log^4n)

O(Tlog4n)，可过。

CODE

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<random>

#include<vector>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 10000005

#define LL long long

#define ULL unsigned long long

#define DB double

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

#define FI first

#define SE second

LL read() {

    LL f=1,x=0;int s = getchar();

    while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}

    while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}

    return f*x;

}

const char sxt[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

ULL readull() {

	ULL x=0;int s = getchar();

	while(s < '0' || s > '9') {if(s < 0) return 0;s = getchar();}

	while(s >= '0' && s <= '9') {x=(x<<3)+(x<<1)+(s^48); s = getchar();}

	return x;

}

void putpos(ULL x) {if(!x)return ;putpos(x>>4);putchar(sxt[x&15]);}

void putnum(ULL x) {

    if(!x) {putchar('0');return ;}

    return putpos(x);

}

void AIput(ULL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;

ULL inv[128];

ULL facf(ULL x) {

	if(!x) return 1ull;

	ULL dp[128][128] = {};

	dp[0][0] = 1;

	for(int i = 1;i <= 126 && i <= x;i ++) {

		for(int j = 1;j <= i;j ++) {

			dp[i][j] = dp[i-1][j] * (i-1+j) + dp[i-1][j-1] * (i-1+j);

		}

	}

	if(!(x&1)) x --;

	ULL n = x/2 + 1;

	ULL ans = 0,pw = 1;

	for(int i = 0;i <= 63 && i <= n;i ++,pw <<= 1) {

		ULL stl = 0;

		ULL c1[128],c2 = 1,tlc2 = 1;

		for(int j = 1;j <= i*2 && j <= n;j ++) {

			c1[j] = n-j+1;

			int b = j,cn = 0;

			while(!(b&1)) b>>=1,cn++;

			for(int k = 1;k <= j && cn;k ++) {

				while(cn && !(c1[k]&1)) c1[k]>>=1,cn --;

			}

			c2 *= inv[b];

			tlc2 *= b;

			if(j > i) {

				ULL C = c2;

				for(int k = 1;k <= j;k ++) C *= c1[k];

				stl += C * dp[i][j-i];

			}

		}

		if(i == 0) stl = 1;

		ans += pw * stl;

	}

	return ans;

}

int main() {

	freopen("multiplication.in","r",stdin);

	freopen("multiplication.out","w",stdout);

	inv[0] = 1;

	for(int i = 1;i <= 128;i += 2) {

		ULL a = i;

		inv[i] = i;

		for(int j = 1;j <= 62;j ++) {

			a = a * a;

			inv[i] *= a;

		}

	}

	int T = read();

	while(T --) {

		ULL N = readull();

		int ct = 0;

		ULL b = 1,as = facf(N);

		for(int i = 1;i < 64;i ++) {

			b <<= 1;

			ct += (N/b) & 3;

			ct &= 3;

			as *= facf(N/b);

		}

		for(int i = 1;i <= ct;i ++) as *= 2ull;

		AIput(as,'\n');

	}

	return 0;

}

【NOI P模拟赛】大阶乘（斯特林数）的相关教程结束。