BZOJ 3240 [Noi2013]矩阵游戏 ——费马小定理 快速幂
2024-08-26 01:25:41
发现是一个快速幂,然而过不去。
怎么办呢?
1.十进制快速幂,可以用来练习卡时。
2.费马小定理,如果需要乘方的地方,可以先%(p-1)再计算,其他地方需要%p,所以需要保存两个数。
然后就是分类讨论a是否为1(等比数列求和时要求a不为1)
然后就是递推了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i)
#define ll long long
const ll md=1000000007;
ll n1,m1,n2,m2,a,b,c,d,len,ans;
char s1[1000005],s2[1000005];
ll qpow(ll a,ll b)
{
ll ret=1;
while (b)
{
if (b&1) (ret*=a)%=md;
(a*=a)%=md;
b>>=1;
}
return ret;
}
ll inv(ll a)
{return qpow(a,md-2);}
int main()
{
scanf("%s",s1+1);
scanf("%s",s2+1);
len=strlen(s1+1); F(i,1,len) n1=(n1*10+s1[i]-'0')%(md-1);
len=strlen(s2+1); F(i,1,len) m1=(m1*10+s2[i]-'0')%(md-1);
len=strlen(s1+1); F(i,1,len) n2=(n2*10+s1[i]-'0')%md;
len=strlen(s2+1); F(i,1,len) m2=(m2*10+s2[i]-'0')%md;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if (a!=1)
{
ll e,f;
e=(qpow(a,m1-1)*c)%md;
f=(((((qpow(a,m1-1)-1+md)%md*b)%md*c)%md*inv(a-1))%md+d)%md;
if (e==1)
{
ll tmp=(1LL+f*n2)%md;
ans=((tmp-d+md)%md*inv(c))%md;
}
else
{
ll tmp=qpow(e,n1)+(((qpow(e,n1)-1+md)%md*f)%md*inv((e-1+md)%md))%md;
ans=((tmp-d+md)%md*inv(c))%md;
}
}
else
{
ll e,f;
e=c; f=(((c*b)%md*(m2-1))%md+d)%md;
if (e==1)
{
ll tmp=(1LL+f*n2)%md;
ans=((tmp-d+md)%md*inv(c))%md;
}
else
{
ll tmp=qpow(e,n1)+(((qpow(e,n1)-1+md)%md*f)%md*inv((e-1+md)%md))%md;
ans=((tmp-d+md)%md*inv(c))%md;
}
}
printf("%lld\n",ans);
}
最新文章
- Spring注入中byType和byName的总结
- Win Form程序线程点点
- 数据库整合数据报表SQL实战
- 作业七:团队项目——Alpha版本冲刺阶段-12
- vs.php调试php使用外部的apache进行调试
- mysql 行转列
- maven总结4
- 【插件开发】—— 1 Eclipse插件开发导盲
- 将Xml或Json生成类的最简单方式
- js获取本月第几周和本年第几周
- Condition-线程通信更高效的方式
- linux下显卡信息的查看
- less可以做什么?less详解!(less嵌套选择器实现纯CSS二级导航)
- thinkphp 迁移数据库 -Phinx 简单说明文档
- js中关于声明提前的几个误区
- 关于UNITY学习,给新生建议
- C语言字符串格式化显示
- JObject 用法 、JProperty 用法、JArray 用法 Linq 转 Json
- [SoapUI] 设置最大等待时间,不断重复的去发送一个request,每次从response中获取一个status,直到这个status从一种状态变成另外一种状态
- HelloAndroid