【杭电多校2020】1005.Fibonacci Sum(数论,公式)
程序员文章站
2022-05-04 19:46:06
题目链接思路:根据斐波那契数列通式结合二次剩余处理求出各部分值,然后再根据杨辉三角展开多项式,最后多项式合并之后可以看做一个与k相关的等比数列,求和即可,中间用到快速幂优化和欧拉降幂并且预处理阶乘及逆元。具体清晰思路–>请移步带佬博客代码:#includeusing namespace std;#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout...
题目链接
思路:
根据斐波那契数列通式结合二次剩余处理求出各部分值,然后再根据杨辉三角展开多项式,最后多项式合并之后可以看做一个与k相关的等比数列,求和即可,中间用到快速幂优化和欧拉降幂并且预处理阶乘及逆元。
具体清晰思路–>请移步带佬博客
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+7;
const double eps=1e-8;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=3.1415926535;
int MOD=1e9+9,p=383008016,A=(p+1ll)*(MOD+1)/2%MOD,B=(1ll+MOD-p)*(MOD+1)/2%MOD;
inline int qpow(int a,int p)
{
int ans=1;
while (p)
{
if(p&1)
{
ans=ans*a%MOD;
}
a=a*a%MOD;
p>>=1;
}
return ans;
}
int fac[N],finv[N],px[N],py[N];
signed main()
{
IOS;
fac[0]=1;
for(int i=1;i<=N;i++)
{
fac[i]=fac[i-1]*i%MOD;
}
finv[N]=qpow(fac[N],MOD-2);
for (int i=N-1;i>=0;i--)
{
finv[i]=finv[i+1]*(i+1)%MOD;
}
int t;
cin>>t;
while(t--)
{
int n,c;
int k;
cin>>n>>c>>k;
c%=MOD-1;
int ans=0,x=qpow(A,c),y=qpow(B,c);
px[0]=py[0]=1;
for(int i=1;i<=k;i++)
{
px[i]=px[i-1]*x%MOD;
py[i]=py[i-1]*y%MOD;
}
for(int i=0;i<=k;i++)
{
int t=((i&1)? MOD-1ll:1ll)*fac[k]%MOD*finv[i]%MOD*finv[k-i]%MOD;
int a=px[k-i]*py[i]%MOD;
if(a==1)
{
ans=(ans+(n+1ll)%MOD*t)%MOD;
}
else
{
ans=(ans+t*(qpow(a,(n+1ll)%(MOD-1))-1ll)%MOD*qpow(a-1,MOD-2))%MOD;
}
}
ans=ans*qpow(p,MOD-1-k)%MOD;
cout<<ans<<endl;
}
return 0;
}
本文地址:https://blog.csdn.net/ACkingdom/article/details/107523439
上一篇: Vue调用Java接口下载文件流
下一篇: 微信小程序自定义底部弹出框功能
推荐阅读
-
【杭电多校2020】1005.Fibonacci Sum(数论,公式)
-
【杭电多校2020】第五场1001.Tetrahedron
-
【杭电多校2020】第二场1001.Total Eclipse(并查集)
-
2020杭电多校第五场 1009 Paperfolding
-
2020杭电多校集训-Distinct Sub-palindromes
-
[杭电多校2020]第一场 1004 Distinct Sub-palindromes
-
2020年杭电多校第五场题解Tetrahedron、Boring Game、Paperfolding
-
2020杭电多校第八场题解
-
2020杭电多校第八场
-
【杭电多校2020】1005.Fibonacci Sum(数论,公式)