题目链接:http://codeforces.com/problemset/problem/963/A

题目大意:就是给了你n,a,b和一段长度为k的只有'+'和‘-’字符串,保证n+1被k整除,让你你计算

解题思路:

暴力肯定超时的,我们可以先计算出0~k-1这一段的值,当做a1,可以发现如果把每段长度为k的段的值当做一个元素,他们之间是成等比的,比值q=(b/a)^k,

然后就直接用等比数列求和公式求出答案即可。昨天把q当成b/a了,我的脑子啊。。。

注意,判断q==1时不能通过判断a==b,而是判断(a/b)^k==1来实现。

代码:

 #include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const LL MOD=1e9+;
const double eps=1e-; string str; LL fpow(LL x,LL n){
LL res=;
while(n>){
if(n&) res=res*x%MOD; //如果二进制最低位为1,则乘上x^(2^i)
x=x*x%MOD; //将x平方并取模
n>>=;
}
return (res%MOD+MOD)%MOD;
} LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(!b){
x=;
y=;
return a;
}
LL gcd=extend_gcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-(a/b)*x;
return gcd;
} LL NY(LL num){
LL x,y;
extend_gcd(num,MOD,x,y);
return (x%MOD+MOD)%MOD;
} int main(){
FAST_IO;
LL n,a,b,k;
cin>>n>>a>>b>>k;
cin>>str;
LL len=(n+)/k;
LL sum=;
for(int i=;i<k;i++){
if(str[i]=='+')
sum=((sum+fpow(a,n-i)*fpow(b,i))%MOD+MOD)%MOD;
else
sum=((sum-fpow(a,n-i)*fpow(b,i))%MOD+MOD)%MOD;
}
LL ans;
//注意,比值q是(b/a)^k而不是(b/a)
LL q=fpow(NY(a),k)*fpow(b,k)%MOD;
if(q!=){
LL _q=NY(q-);
ans=(sum*(fpow(q,len)-)%MOD*_q%MOD+MOD)%MOD;
}
else
ans=sum*len%MOD;
cout<<ans<<endl;
return ;
}

最新文章

  1. less和sass
  2. java JedisUtils工具类
  3. Redis 读后小感
  4. SQL Server 2008 Datetime Cast 成 Date 类型可以使用索引(转载)
  5. 在Windows8 Winrt中 高性能处理多个条件语句 用于实现自定义手势
  6. Java Final, Finally, Finalize
  7. 字符串中符号的替换---replace的用法
  8. 石子合并(四边形不等式优化dp) POJ1160
  9. Flash Recovery Area空间不足导致DB不能打开或hang住处理方法
  10. WCF Restful Service的服务
  11. linux shell数组
  12. activiti的springboot模块
  13. Mxd文档更新比例尺
  14. LogXGEController: Error: XGE version 8.01 (build 1867) or higher is required for XGE shader
  15. SQLI DUMB SERIES-8
  16. OneZero产品视频
  17. Lucene 个人领悟 (二)
  18. POJ 1117 Pairs of Integers
  19. Python的静态方法和类成员方法
  20. Mybatis JPA-集成方案+源码

热门文章

  1. sqoop 补充
  2. Rstdio快捷键总结
  3. C# 在程序中控制IIS服务或应用程序池关闭重启
  4. 应用jfinal时要注意区分Db.query和Db.find
  5. Vue入坑教程(一)——搭建vue-cli脚手架
  6. 设计模式之————依赖注入(Dependency Injection)与控制反转(Inversion of Controller)
  7. 安装python包时遇到&quot;error: Microsoft Visual C++ 9.0 is required&quot;的简答
  8. Docker中执行Shell出现乱码
  9. [整理]ASP.NET vNext学习资源
  10. 【leetcode 简单】 第六十五题 2的幂