脚本宝典收集整理的这篇文章主要介绍了「模拟赛20211030」乘积，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

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

对于 (100%) 的数据，满足 (1le 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)) 层。

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

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

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

但是，使用多项式难免会遇到长度的问题。一个重要的观察则是：由于我们最终对 (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;
}

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

脚本宝典总结

以上是脚本宝典为你收集整理的「模拟赛20211030」乘积全部内容，希望文章能够帮你解决「模拟赛20211030」乘积所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。