洛谷P4925 [1007]Scarlet的字符串不可能这么可爱(计数)

题意

Sol

只要知道“回文连续子串”就能做了吧。。

想要满足这个条件，肯定是不能出现\(aa\)或\(aba\)这种情况

如果没有\(S\)的限制，答案为\(K * (K - 1) * \prod_{i = 3}^n (k - 2)\)

如果有\(S\)的限制就除一个\(K\)

然而考场上没注意到会乘爆long long于是挂乘暴力分。。。。

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int K, L, mod, S, W;

int mul(int a, int b) {

    return a * b % mod;

}

int fastpow(int a, int p) {

    int base = 1; a %= mod;

    while(p) {

        if(p & 1) base = 1ll * base * a % mod;

        a = 1ll * a * a % mod; p >>= 1;

    }

    return base;

}

main() {

    K = read(); L = read(); mod = read();

    S = read(); W = read();

    K %= mod;

    if(S == 0) {

        if(L == 1) cout << K;

        else if(L == 2) cout << K * (K - 1) % mod;

        else cout << 1ll * K * (K - 1) % mod * fastpow(K - 2, L - 2) % mod;

    } else {

        int base = 1;

        if(L == 1) cout << 1;

        else if(L == 2) cout << (K - 1) % mod;

        else {

            base = mul(base, K - 1);

            base = base * fastpow(K - 2, L - 2) % mod;

            cout << base;

        }

    }

}

巴特西

洛谷P4925 [1007]Scarlet的字符串不可能这么可爱(计数)

题意

Sol

最新文章

热门文章