LJJ 学二项式定理

科技前沿 • 2025-04-05 19:05 • 阅读 53

大家好，我是讯享网，很高兴认识大家。

题目：
https://loj.ac/problem/6485

给定 $n,s,a_0,a_1,a_2,a_3$ ，求
$\Big[\sum_{i=0}^{n}{n\choose i}s^ia_{i\;mod\;4}\Big]\;mod\;$

思路：

单位根反演
$[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega^{ki}_n$

$\begin{aligned} &\sum_{i=0}^{n}{n\choose i}s^ia_{i\;mod\;4}\\ =&\sum_{j=0}^{3}a_j\sum_{i=0}^{n}{n\choose i}s^i[i\;mod\;4=j]\\ =&\sum_{j=0}^{3}a_j\sum_{i=0}^{n}{n\choose i}s^i[4|i-j]\\ =&\sum_{j=0}^{3}a_j\sum_{i=0}^{n}\frac{1}{4}{n\choose i}s^i\sum_{k=0}^{3}\omega^{k(i-j)}_4\\ =&\frac{1}{4}\sum_{j=0}^{3}a_j\sum_{k=0}^{3}\omega^{-kj}_4\sum_{i=0}^{n}{n\choose i}s^i\omega^{ki}_4\\ =&\frac{1}{4}\sum_{j=0}^{3}a_j\sum_{k=0}^{3}\omega^{-kj}_4(s\omega^k_4+1)^n \end{aligned}$

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod = ; const int w [] = { 
   1,,,}; ll T,n,s,ans,res,inv; ll a[4]; ll ksm (ll a,ll b) { 
    a%=mod; ll s=1; for (; b; b>>=1,a=a*a%mod) if (b&1) s=s*a%mod; return s; } int main () { 
    scanf("%lld",&T); inv=ksm(4,mod-2); while (T--) { 
    scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&a[0],&a[1],&a[2],&a[3]); ans=0; for (int i=0; i<=3; ++i) { 
    res=0; for (int j=0; j<=3; ++j) res=(res+w[(4-i*j%4)%4]*ksm(s*w[j]+1,n)%mod)%mod; ans=(ans+a[i]*res%mod)%mod; } printf("%lld\n",ans*inv%mod); } return 0; }

讯享网

LJJ 学二项式定理

相关推荐