欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-12 17:48:26
题意 "题目链接" Sol 只要知道“回文连续子串”就能做了吧。。 想要满足这个条件,肯定是不能出现$aa$或$aba$这种情况 如果没有$S$的限制,答案为$K (K 1) \prod_{i = 3}^n (k 2)$ 如果有$S$的限制就除一个$K$ 然而考场上没注意到会乘爆long long于 ......

题意

题目链接

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;
        }
    }
}