博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【LOJ#6485】LJJ 学二项式定理(单位根反演)
阅读量:5366 次
发布时间:2019-06-15

本文共 1286 字,大约阅读时间需要 4 分钟。

【LOJ#6485】LJJ 学二项式定理(单位根反演)

题面

题解

显然对于\(a0,a1,a2,a3\)分开算答案。

这里以\(a0\)为例
\[\begin{aligned} Ans&=\frac{1}{4}a_0\sum_{i=0}^n [4|i]{n\choose i}s^i\\ &=\frac{1}{4}a_0\sum_{i=0}^n{n\choose i}s^i\sum_{j=0}^3 (\omega_4^{j})^i\\ &=\frac{1}{4}a_0\sum_{j=0}^3\sum_{i=0}^n {n\choose i}s^i(\omega_4^j)^i\\ &=\frac{1}{4}a_0\sum_{j=0}^3(s\omega_4^j+1)^n \end{aligned}\]
另外几个只需要把\([4|i]\)变成\([4|(i+k)]\)的形式,然后在计算的时候把\(\omega_4^k\)给提取出来就行了。

#include
#include
using namespace std;#define ll long long#define MOD 998244353inline ll read(){ ll x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int fpow(int a,ll b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}int s,a[4],w,ans;ll n;int main(){ int T=read();w=fpow(3,(MOD-1)/4); while(T--) { n=read();s=read();ans=0; for(int i=0;i<4;++i)a[i]=read(); for(int i=0;i<4;++i) for(int j=0,t=s,ww=1;j<4;++j,t=1ll*t*w%MOD,ww=1ll*ww*w%MOD) ans=(ans+1ll*a[i]*fpow(t+1,n)%MOD*fpow(ww,4-i))%MOD; ans=1ll*ans*fpow(4,MOD-2)%MOD; printf("%d\n",ans); }}

转载于:https://www.cnblogs.com/cjyyb/p/10841160.html

你可能感兴趣的文章
ASP.NET MVC 教程-MVC简介
查看>>
SQL Server索引 - 聚集索引、非聚集索引、非聚集唯一索引 <第八篇>
查看>>
转载:详解SAP TPM解决方案在快速消费品行业中的应用
查看>>
Android OpenGL ES 开发(N): OpenGL ES 2.0 机型兼容问题整理
查看>>
项目中用到的技术及工具汇总(持续更新)
查看>>
【算法】各种排序算法测试代码
查看>>
HDU 5776 Sum
查看>>
201521123044 《Java程序设计》第9周学习总结
查看>>
winfrom 图片等比例压缩
查看>>
人工智能实验报告一
查看>>
用LR12录制app,用LR11跑场景,无并发数限制,已试验过,可行!
查看>>
python 多线程就这么简单(转)
查看>>
oracle 简述
查看>>
ajax如何向后台传递数组,在后台该如何接收的问题(项目积累)
查看>>
Solr之java实现增删查操作
查看>>
httpClient连接工具类实测可用
查看>>
CDOJ 1965 连通域统计【DFS】
查看>>
飞机大战3-我的飞机
查看>>
c#接口
查看>>
MyEclipse部署Jboss出现java.lang.OutOfMemoryError: PermGen space
查看>>