Codeforces Round #475 (Div. 2) C - Alternating Sum

1945 ワード
まず0-k項は次の後(n+1)/k組項が等比数列(比はa^{-k}b^{k})を直接求めることができるが,この場合はこの比が1の特殊な場合も考慮すればよい(a=bの場合はこの比が1になり,取り残したためにめちゃくちゃな場合も比が1になる)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
#define MS(x, y) memset(x, y, sizeof(x))
#define MP(x, y) make_pair(x, y)
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 9;
char S[N];

ll Pow(ll x, ll y) {
    ll result = 1;
    while (y) {
        if (y & 1)
            result = result * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return result;
}
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out1.txt", "w", stdout);
    ll n, a, b, k;
    while (~scanf("%lld %lld %lld %lld %s", &n, &a, &b, &k, S)) {
        ll origin = Pow(a, n);
        ll ans = 0;
        ll aDivide = Pow(a, MOD - 2);
        for (int i = 0; i < k; ++i) {
            if (S[i] == '+')
                ans = (ans + origin) % MOD;
            else
                ans = (ans - origin + MOD) % MOD;
            //      printf("%lld
", origin);
            origin = origin * aDivide % MOD * b % MOD;
        }
        //  printf("%lld
", ans);
        ll mulUnit = Pow(Pow(a, k), MOD - 2) * Pow(b, k) % MOD;
        ll times = (n + 1) / k;
        ll ansUnit;
        if (a == b || mulUnit == 1) {
            ansUnit = times;
        } else {
            ansUnit = (Pow(mulUnit, times) - 1 + MOD) % MOD;
            ansUnit = ansUnit * Pow((mulUnit - 1 + MOD) % MOD, MOD - 2) % MOD;
        }
        printf("%lld
", ans * ansUnit % MOD);
    }
    return 0;
}
/*

5 2 3 3
+-+

5 1 1 3
+-+
*/
CSS設計ネーミング仕様BEM
微信公衆番号録音ファイルは自分が開発したサーバに保存する(amrファイルはmp 3に転送する)