1 #include<cstdio>
 2 #include<cmath>
 3 #include<cctype>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<string>
13 #define lc(a) (a<<1)
14 #define rc(a) (a<<1|1)
15 #define MID(a,b) ((a+b)>>1)
16 #define fin(name)  freopen(name,"r",stdin)
17 #define fout(name) freopen(name,"w",stdout)
18 #define clr(arr,val) memset(arr,val,sizeof(arr))
19 #define _for(i,start,end) for(int i=start;i<=end;i++)
20 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
21 using namespace std;
22 typedef long long LL;
23 const LL MOD=1e9+9;
24 const double eps=1e-10;
25 
26 string str;
27 
28 LL fpow(LL x,LL n){
29     LL res=1;
30     while(n>0){
31         if(n&1) res=res*x%MOD;  //如果二进制最低位为1，则乘上x^(2^i)
32         x=x*x%MOD;                //将x平方并取模
33         n>>=1;
34     }
35     return (res%MOD+MOD)%MOD;
36 }
37 
38 LL extend_gcd(LL a,LL b,LL &x,LL &y){
39     if(!b){
40         x=1;
41         y=0;
42         return a;
43     }
44     LL gcd=extend_gcd(b,a%b,x,y);
45     LL t=x;
46     x=y;
47     y=t-(a/b)*x;
48     return gcd;
49 }
50 
51 LL NY(LL num){
52     LL x,y;
53     extend_gcd(num,MOD,x,y);
54     return (x%MOD+MOD)%MOD;
55 }
56 
57 int main(){
58     FAST_IO;
59     LL n,a,b,k;
60     cin>>n>>a>>b>>k;
61     cin>>str;
62     LL len=(n+1)/k;
63     LL sum=0;
64     for(int i=0;i<k;i++){
65         if(str[i]=='+')
66             sum=((sum+fpow(a,n-i)*fpow(b,i))%MOD+MOD)%MOD;
67         else
68             sum=((sum-fpow(a,n-i)*fpow(b,i))%MOD+MOD)%MOD;
69     }
70     LL ans;
71     //注意，比值q是(b/a)^k而不是(b/a)
72     LL q=fpow(NY(a),k)*fpow(b,k)%MOD;
73     if(q!=1){
74         LL _q=NY(q-1);
75         ans=(sum*(fpow(q,len)-1)%MOD*_q%MOD+MOD)%MOD;
76     }
77     else
78         ans=sum*len%MOD;
79     cout<<ans<<endl;
80     return 0;
81 }

优质内容筛选与推荐>>
1、添加应用栏
2、学生表 课程表 成绩表 教师表 50个常用sql语句
3、Python--网络编程-----解决粘包问题-简单版
4、Unity3D脚本中文系列教程(十)
5、PHP介绍