洛谷P4925 [1007]Scarlet的字符串不可能这么可爱(计数)
程序员文章站
2022-11-08 22:51:47
题意 "题目链接" 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; } } }
上一篇: 银鱼干是海鱼还是淡水鱼
下一篇: AI怎样制作立体感爆棚的线条海报?