【逆元+等比数列】CF963A Alternating Sum

爱被打了一巴掌 2024-03-22 16:09 8阅读 0赞

[Alternating Sum - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][Alternating Sum - _ _ _ _luogu.com.cn]

题意：

![65e99a6803354ac983abc591658ea7f2.png][]

思路：

![d61acd9f3048401492e5cf5d1fef3bbf.jpeg][]

![6740053c8db4479384e9e3aede89d349.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=3e6+10;
    const int mxe=3e5+10;
    const int mod=1e9+9;
    
    string s;
    int n,a,b,k;
    int c[mxn];
    
    int ksm(int a,int b){
        int res=1ll;
        while(b){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
    void solve(){
        cin>>n>>a>>b>>k;
        cin>>s;
        for(int i=0;i<=k-1;i++){
            if(s[i]=='+') c[i]=1;
            else c[i]=-1;
        }
        int sum=0ll;
        for(int i=0;i<=k-1;i++) sum=(sum+c[i]*ksm(a,n-i)%mod*ksm(b,i)%mod+mod)%mod;
        int ans=1ll;
        if(ksm(ksm(b,ksm(a,mod-2)),k)==1ll) ans=(sum*((n+1)/k)%mod+mod)%mod;
        else{
            int q=(ksm(b,k)*ksm(ksm(a,k),mod-2)%mod+mod)%mod;
            ans=(sum*(1-ksm(q,(n+1)/k))%mod*ksm((1-q),mod-2)%mod+mod)%mod;
        }
        cout<<(ans%mod+mod)%mod<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Alternating Sum - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/CF963A
[65e99a6803354ac983abc591658ea7f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d3078a50f5564ab48be06ceee3987c5d.png
[d61acd9f3048401492e5cf5d1fef3bbf.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/12d69d6e6d7b4588b063a18a92e17f47.png
[6740053c8db4479384e9e3aede89d349.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d142e22c7a16450fae1b59ba5cb965e2.png