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,……项系数的和，那么我们就只需要计算 $$ \frac{1}{4}(f(\omega_{4}^{0})+f(\omega_{4}^{1})+f(\omega_{4}^{2})+f(\omega_{4}^{3}))$$的值即可 好了如果你还没有懵逼的话 我们继续接下来的推倒过程 设 $$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好了~~ ~~代码极短~~ 上代码~ ```C #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; } ```