Codeforces 964 C. Alternating Sum (求和+逆元)

本文主要是介绍Codeforces 964 C. Alternating Sum (求和+逆元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

You are given two integers a and b. Moreover, you are given a sequence s0,s1,…,sn. All values in s are integers 1 or −1. It’s known that sequence is k-periodic and k divides n+1. In other words, for each k≤i≤n it’s satisfied that $s_i=s_{i−k}.$
Find out the non-negative remainder of division of $\sum_{i=0}^{n}s_ia^{n-i}b^i$ by 109+9.
Note that the modulo is unusual!

Input

The first line contains four integers n,a,b and k(1≤n≤109,1≤a,b≤109,1≤k≤105).
The second line contains a sequence of length k consisting of characters ‘+’ and ‘-‘.
If the i-th character (0-indexed) is ‘+’, then si=1, otherwise si=−1.
Note that only the first k members of the sequence are given, the rest can be obtained using the periodicity property.

Output

Output a single integer — value of given expression modulo ${10}^9+9.$

Examples

input
2 2 3 3
+-+
output
7
input
4 1 5 1
-
output
999999228

题目描述

求 $\sum_{i=0}^{n}s_ia^{n-i}b^i$ ，其中si由给定的符号字符串确定，若对应位置为‘+’，则si=1,否则si=-1，字符串的长度为k，当i大于k时，从头循环获取对应位置.

解题思路

首先看到k的范围是1e5，便可以考虑从这里入手去求解，当n>k时，可以发现每k个连续的数之间成比例，且比值为 $\frac{b^k}{a^k}$ ，这样便可以构成一个公比为 $\frac{b^k}{a^k}$ 的，项数为num=(n+1)/k 的等比数列，从头循环一遍k便可得出首项，然后等比数列求和.剩余的(n+1)-num*k即无法构成等比数列的数再单独遍历求和即可.
Ps：求逆元是肯定的，但是要注意判断公比的逆元是否为1.不要傻乎乎的在求逆元之前判断(ಥ﹏ಥ)C题又没达成(ಥ﹏ಥ)

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1e5+7;
const ll mod=1e9+9;
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
char str[maxn];
ll quick_pow(ll a,ll b)
{ll ans=1;while(b){if(b%2)ans=(ans*a)%mod;a=(a*a)%mod;b/=2;}return ans;
}
int main()
{IO;ll n,a,b,k;cin>>n>>a>>b>>k>>str;ll ans=0;ll res=0;ll x=quick_pow(a,n),xx=quick_pow(a,mod-2),xxx=1;  //a^n,a的逆元ll y=quick_pow(b,n),yy=quick_pow(b,mod-2),yyy=1;  //同上int mark;for(int i=0; i<k; i++)      //前k个的和{if(str[i]=='+') mark=1;else mark=-1;res=(res+mark*x*yyy)%mod;x=(x*xx)%mod;yyy=(yyy*b)%mod;}ll num=(n+1)/k;                              //该等比数列含有num个项ll divide=quick_pow(quick_pow(a,k),mod-2);   //a^k的逆元ll mul=quick_pow(b,k);                       //b^kll q=mul*divide%mod;                         //公比if(q==1)ans=(num*res)%mod;elseans=(res*((1-quick_pow(q,num))%mod)%mod*quick_pow(1-q,mod-2)%mod+mod)%mod;num=(n+1)-num*k;                             //除去可构成等比数列之后的剩余项ll id=num-1;                                 //由后向前加和res=0;for(ll i=0; i<num; i++){if(str[id]=='+') mark=1;else mark=-1;res=(res+mark*y*xxx)%mod;y=(y*yy)%mod;xxx=(xxx*a)%mod;id--;}ans=((ans+res)%mod+mod)%mod;cout<<ans<<endl;return 0;
}