题目;这里写链接内容 题意：求 这里si是给定的一串正负号组成的字符，表示1~k项的符号，n+1可以整除k，即所求数列的符号是k循环的，a[i]=a[i+k]。 思路：由题意，很明显，这是一个等比数列，先用快速幂求出前k项的和a1，即等比数列的首项，n+1/k即是长度，套用等比数列求和公式即可。要用到逆元。
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> using namespace std; const int maxn = 1e5+10; typedef long long ll; const ll mod=1e9+9; char s[maxn]; ll quick_pow(ll x,ll y){ ll ans=1; x%=mod; while (y){ if(y%2)ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } int main(){ ll n,a,b,k; scanf("%lld%lld%lld%lld",&n,&a,&b,&k); scanf("%s",s); ll cur=0; for(int i=0;i<k;i++){//求前k项和 int x=s[i]=='+'?1:-1; cur=(cur+x*quick_pow(a,n-i)*quick_pow(b,i)%mod+mod)%mod; } ll q=b*quick_pow(a,mod-2)%mod;//比例q=（b/a）^k%mod这里先求（b/a）%mod，注意逆元 q=quick_pow(q,k)%mod; ll num=(n+1)/k; if(q==1){ cur=cur*num%mod; }else { ll x=(1-quick_pow(q,num))*quick_pow(1-q,mod-2)%mod;//等比数列公式，有可能出现负数 while (x<0)x+=mod; cur=cur*x%mod; } printf("%lld\n",cur); return 0; }