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

题目大意：问字符集大小为$k$，长度为$L$的字符串，且没有长度超过$1$的回文段的个数。规定第$s（若为0则无限制）$位为$w$。

题解：懒得写了，根据是否有限制分类讨论

卡点：中途有个地方忘记取模

 

C++ Code：

#include <cstdio>
long long k, L, mod, s;
inline long long pw(long long base, long long p) {base %= mod;long long res = 1;for (; p; p >>= 1, base = base * base % mod) if (p & 1) res = res * base % mod;return res;
}
int main() {scanf("%lld%lld%lld%lld%*d", &k, &L, &mod, &s);if (s) {if (L == 1) puts("1");else if (L == 2) printf("%lld\n", (k - 1) % mod);else printf("%lld\n", (k - 1) % mod * pw(k - 2, L - 2) % mod);} else {if (L == 1) printf("%lld\n", k % mod);else if (L == 2) printf("%lld\n", k % mod * (k - 1) % mod);else printf("%lld\n", k % mod * ((k - 1) % mod) % mod * pw(k - 2, L - 2) % mod);}return 0;
}

　　

转载于:.html