【BZOJ1436】Poi2003 Trinomial

2015.08.13 10:57 Thu | 35次阅读 | 旧日oi | 固定链接 | 源码

Description

考虑一个多项式(x2 + x + 1)^n. 我们对展开式中的系数ci 很感兴趣: C0 + C1x + C2x^2 + ... + C2n x^2n 举个例子, (x^2 + x + 1)^3 = 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6.

题解

首先推出系数公式:
$(x^2+x+1)^n = \sum_{i=0}^{n} C(n, i) \sum_{j=0}^{i} C(i, j) x^{2i+j}$
对于第k项,他的系数为
然后根据卢卡斯定理,可以转化为
$ans = (\sum_{j=0}^{k}C(n, ((k-j) / 2)) C(n/3, ((k-j)/2) / 3) C(((k-j) / 2), j) C(((k-j) / 2) / 3, j / 3))$
考虑枚举(k-j)/2%3的余数,这是一个3个n=3以内的组合数问题和3个规模为n/3的子问题,然后对应乘起来,但是这样的复杂度还是O(n)的,然而因为那三个组合数问题有很大几率是0,所以那三个子问题有很多是不必要算的,所以复杂度是个玄学。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
int T;
ll n,k;
int c[3][3]=
{
    {1,0,0},
    {1,1,0},
    {1,2,1}
};
int C(ll n,ll m)
{
    if(m>n) return 0;
    return m==0?1:(m==1?n%3:n*(n-1)/2%3);
}
int calc(ll n,ll k)
{
    if(k<=2)
    {
        int sum=0;
        for(int i=0;i<=k;i++) sum+=C(n,i)*C(i,k-i);
        return sum%3;
    }
    int t1=c[n%3][0]*c[0][(k-0)%3],k1=t1?calc(n/3,(k-0)/3):0;
    int t2=c[n%3][1]*c[1][(k-1)%3],k2=t2?calc(n/3,(k-1)/3):0;
    int t3=c[n%3][2]*c[2][(k-2)%3],k3=t3?calc(n/3,(k-2)/3):0;
    return (t1*k1+t2*k2+t3*k3)%3;
}
int main()
{
    for(cin>>T;T;T--)
    {
        scanf("%lld%lld",&n,&k);
        printf("%d\n",calc(n,k));
    }
}```