May 1, 2019 由 小羊
题目需要求的数字是将 个球放进 个盒子中,每个盒子中 个球。
考虑盒子的顺序,考虑盒子内球的顺序,就是先将所有的球作一个排列,有 种方法;考虑盒子的顺序,但将每个盒子中两球的位置忽略,那么每种方案会重复 次;不考虑盒子的顺序,那么每种真实方案还会再重复 次。于是,最后答案就是
我们可以构造这样一个多项式:
则 。由于取模是 ,那么上述多项式至多只有 64 项。然后我们可以发现,
于是也可以很方便算出 ,然后就可以愉快的进行倍增啦!
这其中涉及到了一个问题:多项式变量线性变换。记 有如下关系。
这道题就到这里啦~
#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;
}