公司网站内容如何做,wordpress退货插件,北京建站公司做网站价格,东台做网站找哪家好昨天不该早点走的.... 首先操作限制实际上是一个回文限制 每个$b[i] - b[i - 1]$互不干扰#xff0c;不妨设这个串关于中心点对称的这么一对区间的串分别为$(S_1, S_2)$ 题目的限制相当与存在$(T_1, T_2)$使得$T_1 inv(S_2) \;and\;T_2 inv(S_1)$ 考虑一对串$(S_1, S_2)$被计…昨天不该早点走的.... 首先操作限制实际上是一个回文限制 每个$b[i] - b[i - 1]$互不干扰不妨设这个串关于中心点对称的这么一对区间的串分别为$(S_1, S_2)$ 题目的限制相当与存在$(T_1, T_2)$使得$T_1 inv(S_2) \;and\;T_2 inv(S_1)$ 考虑一对串$(S_1, S_2)$被计数多少次我们分类讨论一下 一个长为$L$的子串的方案数为$S^L$即为$f(L)$ 一个长为$L$,字符集为$S$的区间形成回文串的方案数为$S^{\frac{L 1}{2}}$记为$g(L)$ 如果$(S_1, S_2)$中有两个回文串会被算重0次否则都会被算重1次 那么方案数为$(f(L)^2 - g(L)^2) / 2 g(L) * g(L)$ 化简一下$f(L) * (f(L) 1) / 2$ 复杂度$O(n \log n)$ #include vector
#include cstdio
#include cstring
#include iostream
#include algorithm
namespace remoon {#define re register#define de double#define le long double#define ri register int#define ll long long#define sh short#define pii pairint, int#define mp make_pair#define pb push_back#define tpr template typename ra#define rep(iu, st, ed) for(ri iu st; iu ed; iu )#define drep(iu, ed, st) for(ri iu ed; iu st; iu --) extern inline char gc() {static char RR[23456], *S RR 23333, *T RR 23333;if(S T) fread(RR, 1, 23333, stdin), S RR;return *S ;}inline int read() {int p 0, w 1; char c gc();while(c 9 || c 0) { if(c -) w -1; c gc(); }while(c 0 c 9) p p * 10 c - 0, c gc();return p * w;}int wr[50], rw;#define pc(iw) putchar(iw)tpr inline void write(ra o, char c \n) {if(!o) pc(0);if(o 0) o -o, pc(-);while(o) wr[ rw] o % 10, o / 10;while(rw) pc(wr[rw --] 0);pc(c);}tpr inline void cmin(ra a, ra b) { if(a b) a b; }tpr inline void cmax(ra a, ra b) { if(a b) a b; } tpr inline bool ckmin(ra a, ra b) { return (a b) ? a b, 1 : 0; }tpr inline bool ckmax(ra a, ra b) { return (a b) ? a b, 1 : 0; }
}
using namespace std;
using namespace remoon;#define mod 998244353
#define iv2 499122177
#define sid 200050inline int fp(int a, int k) {int ret 1;for( ; k; k 1, a 1ll * a * a % mod)if(k 1) ret 1ll * ret * a % mod;return ret;
}int n, m, S;
int b[sid];int main() {n read(); m read(); S read();rep(i, 1, m) b[i] read(); int ans fp(S, n - (b[m] * 2));rep(i, 1, m) {int L b[i] - b[i - 1];ans 1ll * ans * fp(S, L) % mod * (fp(S, L) 1) % mod * iv2 % mod;}write(ans);return 0;
} 转载于:https://www.cnblogs.com/reverymoon/p/9779929.html
