HDU6481 A Math Problem

May 1, 2019 由 小羊

题目需要求的数字是将 $2n$ 个球放进 $n$ 个盒子中，每个盒子中 $2$ 个球。

考虑盒子的顺序，考虑盒子内球的顺序，就是先将所有的球作一个排列，有 $(2n)!$ 种方法；考虑盒子的顺序，但将每个盒子中两球的位置忽略，那么每种方案会重复 $2^k$ 次；不考虑盒子的顺序，那么每种真实方案还会再重复 $n!$ 次。于是，最后答案就是

$F(n) = \frac{(2n)!}{n!2^k} = \prod_{i=1}^n (2i-1)$

我们可以构造这样一个多项式：

$f_n(x) = \prod_{i=1}^n (2x + 2i-1)$

则 $F(n) = f_n(0)$。由于取模是 $2^{64}$，那么上述多项式至多只有 64 项。然后我们可以发现，

$f_{2n}(x) = f_n(x) f_n(x+n)$

于是也可以很方便算出 $f_{2n+1}(x)$，然后就可以愉快的进行倍增啦！

这其中涉及到了一个问题：多项式变量线性变换。记 $F(x) = \sum f_i x^i, F(x+n) = G(x) = \sum g_i x^i$ 有如下关系。

$g_i = \sum_{j=i}^\infty C_j^i f_j n^{j-i}$

这道题就到这里啦~

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
lld C[64][64], jc[64];

struct poly
{
    lld x[64];

    poly() { for (int i = 0; i < 64; i++) x[i] = 0; }
    poly(lld c1, lld c0) : poly() { x[1] = c1, x[0] = c0; }
    lld operator()(int k) const { return x[k]; }
    lld &operator()(int k) { return x[k]; }

    poly operator*(const poly &b) const
    {
        poly c;
        for (int i = 0; i < 64; i++)
            for (int j = 0; j <= i; j++)
                c(i) += x[j] * b(i-j);
        return c;
    }

    poly moveto(lld n)
    {
        poly ans;
        for (int i = jc[0] = 1; i < 64; i++)
            jc[i] = jc[i-1] * n;
        for (int i = 0; i < 64; i++)
            for (int j = i; j < 64; j++)
                ans(i) += x[j] * jc[j-i] * C[j][i];
        return ans;
    }
};

map<lld, poly> cache;

poly solve(lld n)
{
    if (cache.count(n)) return cache[n];
    poly half = solve(n / 2);
    half = half * half.moveto(n / 2);
    if (n & 1) half = half * poly(2, n*2-1);
    return cache[n] = half;
}

void init()
{
    poly Px(0, 1);
    cache[0] = Px;

    C[0][0] = C[1][0] = C[1][1] = 1;
    for (int n = 2; n < 64; n++)
    {
        C[n][0] = C[n][n] = 1;
        for (int m = 1; m < n; m++)
            C[n][m] = C[n-1][m-1] + C[n-1][m];
    }
}

int main()
{
    init();
    int T; lld n;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%lld", &n);
        printf("%llu\n", solve(n)(0));
    }

    return 0;
}