loj6485 LJJ学二项式定理

· · 个人记录

单位根反演苟逼题……

题意简单明了算数

求

\sum_{i=0}^{n}C_{n}^{i}S^{i}A_{i\%4}

膜998244353的值

其中n<10^{18}

这题不知道单位根反演的就凉了……

然后简单的说一下思路

首先我们发现由于a_{0},a_{1},a_{2},a_{4}都是输入的所以说我们肯定是分情况讨论一波，每个a后边是单独算的

说白了就是求

\sum_{d=0}^{3}A_{d}\sum_{i=0}^{n}C_{n}^{i}S^{i}[i\%4==d]

这个东西的值

接下来的操作就是生成函数那一套理论了……(生成函数真是万能)

我们发现要求的式子和这个式子非常像

\sum_{i=0}^{n}C_{n}^{i}S^{i}

然后由于需要使用生成函数我们把他搞成形式幂级数(这个词仅仅装x用，不理解也没关系)的形式

也就是在每一项后面补一个x^{i}这样，这个数列就变成了一只多项式

\sum_{i=0}^{n}C_{n}^{i}S^{i}x^{i}

但是显然这个式子不能表示成一个简单易懂的多项式

所以考虑求这个数列翻转之后的对应的多项式是什么

\sum_{i=0}^{n}C_{n}^{i}S^{n-i}x^{i}

这是什么？二项式定理啊!题目都提醒你了!

所以

(x+S)^{n}=\sum_{i=0}^{n}C_{n}^{i}S^{n-i}x^{i}

好了这东西有什么用呢？

还记得ntt/fft吗？还记得ntt/fft最后一步点值表达转成系数表达的时候证明了什么吗？

你肯定忘了

各大博客的证明都是根据这个式子证明出来的

\frac{1}{n}\sum_{j=0}^{n-1}(\omega_{n}^{k})^{j}=[n|k]

即n是k的倍数的时候上面的式子是1否则是0

这个式子的证明也不是很难，就是套一波等比数列求和公式即可~

然而这个东西其实非常重要……(但是学ntt的时候绝对是忙着抄板子了)

因为通过上边那个式子，我们可以搞出一个被称为单位根反演的非常nb的东西

大概长这样

若

f(x)=\sum_{i=0}^{n}a_{i}x^{i}

则

\sum_{i=0}^{n}a_{i}[i|d]=\frac{1}{d}\sum_{p=0}^{d-1}f(\omega_{d}^{p})

证明？

把左边式子中的[i|d]换成

\frac{1}{d}\sum_{j=0}^{d-1}(\omega_{d}^{i})^{j}

然后我们有

\frac{1}{d}\sum_{i=0}^{n}a_{i}\sum_{j=0}^{d-1}(\omega_{d}^{i})^{j}

交换一下求和号

\frac{1}{d}\sum_{j=0}^{d-1}\sum_{i=0}^{n}a_{i}(\omega_{d}^{i})^{j}

如果我们令f(x)中的表达式中的x=\omega_{d}^{i}

则有

f(\omega_{d}^{i})=\sum_{i=0}^{n}a_{i}(\omega_{d}^{i})^{j}

代入一下就得到了

\sum_{i=0}^{n}a_{i}[i|d]=\frac{1}{d}\sum_{p=0}^{d-1}f(\omega_{d}^{p})

简单来说，比如说我们要求这个多项式第0,4,8,12,16,……项系数的和，那么我们就只需要计算

好了如果你还没有懵逼的话 我们继续接下来的推倒过程 设 $$f(x)=(x+S)^{n}=\sum_{i=0}^{n}C_{n}^{i}S^{n-i}x^{i}

然后我们要求的是

\sum_{d=0}^{3}A_{d}\sum_{i=0}^{n}C_{n}^{i}S^{i}[i\%4==d]

把整个序列倒过来得到

\sum_{d=0}^{3}A_{d}\sum_{i=0}^{n}C_{n}^{i}S^{n-i}[(n-i)\%4==d]

然后稍作调整

\sum_{d=0}^{3}A_{(n+d)\%4}\sum_{i=0}^{n}C_{n}^{i}S^{n-i}[i\%4==d]

接下来假设我们只求d=0时式子的值

A_{n\%4}\sum_{i=0}^{n}C_{n}^{i}S^{n-i}[i\%4==0]

换句话说就是

A_{n\%4}\sum_{i=0}^{n}C_{n}^{i}S^{n-i}[i|4]

似乎可以直接套刚才的公式？

\frac{1}{4}A_{n\%4}(f(\omega_{4}^{0})+f(\omega_{4}^{1})+f(\omega_{4}^{2})+f(\omega_{4}^{3}))

其中f(x)=(x+s)^{n}

很好，快速幂就能搞定了！

问题来了要是i膜4余1,2,3而不是余0呢？

抱歉，不会

其实是有办法做的

我们的确只能处理i是4的倍数时这些系数的和

但是……，我们可以想办法把余某一个数变成膜4为0

比如说，我们将这个多项式整体平移一位，这样原来余1的项就变成了膜4为0 的项，接下来就可以用之前的套路了

那么多项式怎么平移一位呢？

乘x啊

所以最后答案就变成了

\frac{1}{4}\sum_{d=0}^{3}A_{(n+d)\%4}\sum_{i=0}^{3}f(\omega_{4}^{i})(\omega_{4}^{i})^{d} \frac{1}{4}\sum_{d=0}^{3}A_{(n+d)\%4}\sum_{i=0}^{3}(\omega_{4}^{i}+S)^{n}(\omega_{4}^{i})^{d}

搞定……

不要惊讶,我们的每一步推理都是有理有据的

所以尽管这两个和式没啥关系，但是算出来的数字确实是一样的……

于是我们成功将一个O(nlogn)的式子强行化成了O(logn)的式子

直接愉快的快速幂就行了~

数学真珂啪还是学OI好了

代码极短

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;const ll mod=998244353;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
ll w[4]={1,911660635,998244352,86583718};ll a[4];ll s;ll res;ll n;ll f[4];int T;
int main()
{
    scanf("%d",&T);
    for(int z=1;z<=T;z++)
    {
        scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&a[0],&a[1],&a[2],&a[3]);
        for(int i=0;i<4;i++)f[i]=po((w[i]+s)%mod,n);res=0;
        for(int i=0;i<4;i++)
        {
            ll ret=0;for(int j=0;j<4;j++)(ret+=f[j])%=mod;
            for(int j=0;j<4;j++)(f[j]*=w[j])%=mod;(res+=ret*a[(n+i)%4])%=mod;           
        }printf("%lld\n",res*748683265%mod);
    }return 0;
}