CF963A Alternating Sum
CF963A Alternating Sum
数论题。
发现我数学好菜所以补一补（
题意： \(\sum_{i = 0}^{n} s_i a^{n - i}b^i\) 求这个式子模 \(10^9+9\) 的值，\(s_i\) 的周期为\(k\)。
\(k\le10^5\)，所以 \(0\sim k-1\) 直接求，对于后面的，你发现前一个周期的和，假设是 \(sum\)，那么下一个周期的和就是 \(sum*b^k/a^k\)。
那么转化成等比数列求和了，注意公比是 \(1\) 时要特判，不然就会wa on #9了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+9;
int n,a,b,k,sum;
char s[N];
int kasumi(int a,int b)
{
a%=mod;
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int main()
{
scanf("%d%d%d%d",&n,&a,&b,&k);
scanf("%s",s);
for(int i=0;i<k;i++)
{
if(s[i]=='+')sum=1ll*(sum+1ll*kasumi(a,n-i)*kasumi(b,i)%mod)%mod;
else sum=1ll*(sum+mod-1ll*kasumi(a,n-i)*kasumi(b,i)%mod)%mod;
}
int d=1ll*kasumi(b,k)*kasumi(kasumi(a,k),mod-2)%mod;
if(d==1)printf("%d",1ll*sum*(n+1)%mod*kasumi(k,mod-2)%mod);
else printf("%d",1ll*sum*(kasumi(d,(n+1)/k)+mod-1)%mod*kasumi(d-1,mod-2)%mod);
return 0;
}