题目

给定正整数 \(n\)，求 \(n!\) 在 16 进制下去掉末尾的 0 之后的末 16 位。

对于 \(100\%\) 的数据，满足 \(1\le n<2^{64}\)。

分析

设 \(\bold{v}_p(x)\) 表示 \(x\) 中含因子 \(p\) 的个数。

首先考虑直接计算 \(\frac{n!}{2^{\bold{v}_2(n!)}}\)；在此之后，由于答案在 16 进制下去掉了末尾 0，所以我们需要修正结果，最终的答案就应该是 \(\frac{n!}{2^{\bold{v}_2(n!)}}\times 2^{\bold{v}_2(n!)\bmod 4}\)。

类似于扩展卢卡斯的思想，我们可以对于 \([1,n]\) 奇偶分类。对于奇数，直接计算乘积；对于偶数，则除去因子 2 得到了相似的子问题。这样我们只会递归 \(O(\log n)\) 层。

于是，现在的问题变成了，如何快速求出：

\[f_n=\prod_{k=0}^{n-1}(2k+1) \]

一个比较容易想到的思路是，使用倍增。将问题描述为多项式的形式：

\[\begin{aligned} F_n(x)&=\prod_{k=0}^{n-1}(2x+2k+1)\\ f_n&=F_n(0) \end{aligned} \]

这样，下指标的加法就可以被描述为多项式平移后卷积：

\[F_{i+j}(x)=F_i(x)\cdot F_{j}(x+i) \]

但是，使用多项式难免会遇到长度的问题。一个重要的观察则是：由于我们最终对 \(2^{64}\) 取模，而我们的 \(x\) 自带 \(2\) 的系数，所以多项式的次数不超过 63！

因此，容易想到对于下指标倍增。之后可以根据下指标的加法，求出任意的 \(f_n\)。利用 \(f_n\) 则不难求出 \(\frac{n!}{2^{\bold{v}_2(n)}}\)，再求一下 \(\bold v _2(n)\bmod 4\) 即可。

小结：

1. 注意观察有效的范围，从而减少运算，提高效率。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef unsigned long long ull;

const int MAXN = 70;

template<typename _T>
void read( _T &x )
{
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
void write( _T x )
{
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) write( x / 10 );
    putchar( x % 10 + '0' );
}

char alph[] = "0123456789ABCDEF";

ull C[MAXN][MAXN];
ull F[MAXN][MAXN];
ull G[MAXN], pw[MAXN];

ull N;

const int L = 64;

ull Evaluate( const ull *f, const ull x )
{
    ull ret = 0, cur = 1;
    for( int k = 0 ; k < L ; k ++, cur *= x )
        ret += cur * f[k];
    return ret;
}

void Mul( ull *ret, const ull *A, const ull *B )
{
    static ull tmp[MAXN] = {};
    for( int i = 0 ; i < L ; i ++ ) tmp[i] = 0;
    for( int i = 0 ; i < L ; i ++ )
        for( int j = 0 ; j < L ; j ++ )
            tmp[i + j] += A[i] * B[j];
    for( int i = 0 ; i < L ; i ++ ) ret[i] = tmp[i];
}

void Init( const int lim = 64 )
{
    for( int i = 0 ; i < L ; i ++ )
    {
        C[i][0] = C[i][i] = 1;
        for( int j = 1 ; j < i ; j ++ )
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    F[0][0] = 1, F[0][1] = 2;
    for( int i = 0 ; i < lim - 1 ; i ++ )
    {
        pw[0] = 1;
        for( int j = 1 ; j < L ; j ++ )
            pw[j] = pw[j - 1] * ( 1llu << i );
        for( int j = 0 ; j < L ; j ++ )
        {
            G[j] = 0;
            for( int k = j ; k < L ; k ++ )
                G[j] += F[i][k] * pw[k - j] * C[k][j];
        }
        Mul( F[i + 1], F[i], G );
    }
}

ull Query( const ull n )
{
    if( n < 1 ) return 1; ull ret = 1;
    for( int k = 0 ; k < 64 ; k ++ )
        if( n >> k & 1 ) ret *= Evaluate( F[k], n - ( ( n >> k ) << k ) );
    return ret;
}

int main()
{
    freopen( "multiplication.in", "r", stdin );
    freopen( "multiplication.out", "w", stdout );
    Init();
    int T; read( T );
    while( T -- )
    {
        read( N ); ull ans = 1;
        for( int k = 0 ; k < 64 ; k ++ )
            ans *= Query( ( ( ( N >> k ) - 1 ) >> 1 ) + 1 );
        int lst = 0;
        for( ull x = N ; x ; ) ( lst += ( x >>= 1 ) % 4 ) %= 4;
        ans <<= lst; bool fir = false;
        for( int k = 15 ; ~ k ; k -- )
        {
            unsigned tmp = ans >> ( k << 2 ) & 15;
            if( ! tmp ) fir ? putchar( '0' ) : 1 + 1 == 2;
            else fir = true, putchar( alph[tmp] );
        }
        puts( "" );
    }
    return 0;
}

------------恢复内容结束------------