HDU6481 A Math Problem

题目需要求的数字是将 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;
}

“HDU6481 A Math Problem”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注