BZOJ 5302 奇怪的背包
容易发现，在模 $P$ 意义下，一个数 $x$ 实际的贡献是 $(x, P)$，同时对于多个数来说，其贡献为这些数的 gcd。那么题目转化成给你 $n$ 个 $P$ 的约数，每次询问有多少种选择数的方案使得方案里所有数的 gcd 为某个数的约数。
这个时候就转化成了经典的容斥问题，利用莫比乌斯函数可以方便的在 $n^2$ 的时间内计算出来。同时我们发现，$P$ 的约数数量级在 $\frac{\sqrt P}{ \log P}$ 以内，所以不同的数是远小于 $n$ 这个级别的。因此我们可以在 $\frac{P}{\log ^2 P}$的时间内处理出答案，同时在这个时间内预处理出所有询问，即可做到 $O(1)$ 回答每个询问。
时间复杂度 $O(n + Q + \frac{P}{ \log ^2 P})$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add(a, b)
#define cpop(a,b) a = pop(a, b)
#define cmul(a,b) a = mul(a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define bin(i) (1 << (i))
#define SZ(x) (int)x.size()
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }
const int mod = 1e9 + 7;
const int MAXN = 2e6 + 5;
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}
int qpow(int a, int b){
int c = 1;
while (b) {
if (b & 1) cmul(c, a);
cmul(a, a); b >>= 1;
}
return c;
}
int gcd(int a, int b){return !b ? a : gcd(b, a % b);}
int N, Q, P, num[MAXN], cnt = 0, f[MAXN], g[MAXN], mu[MAXN];
map<int, int> ID;
int main(){
N = read(); Q = read(); P = read();
int m = sqrt(P);
up (i, 1, m) if (P % i == 0) {
num[++cnt] = i;
if (i * i != P) num[++cnt] = P / i;
}
sort(num + 1, num + cnt + 1);
up (i, 1, cnt) ID[num[i]] = i;
up (i, 1, cnt) {
mu[i] = 1;
down (j, i - 1, 1) if (num[i] % num[j] == 0) {
int x = num[i] / num[j];
if (num[j] % x == 0) mu[i] = 0;
else mu[i] = pop(0, mu[j]);
break;
}
}
while (N--) {
int x = read();
cadd(g[ID[gcd(P, x)]], 1);
}
up (i, 1, cnt) {
int sum = 0;
up (j, i, cnt) if (num[j] % num[i] == 0) cadd(sum, g[j]);
g[i] = sum;
}
up (i, 1, cnt) g[i] = pop(qpow(2, g[i]), 1);
up (i, 1, cnt) up (j, i, cnt) if (num[j] % num[i] == 0) {
int x = ID[num[j] / num[i]];
cadd(f[i], mul(g[j], mu[x]));
}
up (i, 1, cnt) {
g[i] = f[i];
f[i] = 0;
}
up (i, 1, cnt) up (j, i, cnt) if (num[j] % num[i] == 0) cadd(f[j], g[i]);
up (i, 1, Q) {
int x = read(); x = gcd(x, P);
printf("%d\n", f[ID[x]]);
}
return 0;
}
BZOJ 5303 反色游戏
首先很显然，我们把每条边看做一个长度为 $n$ 的$0/1$ 向量，在其连接的两个点的位置上为 $1$ ，其余地方为 $0$。那么任意一个方案即为这些 $0/1$向量的异或和。我们用线性基维护，判定给出的方案是否合法即可，我们令线性基的大小为 $w$，那么如果合法，答案为 $2^{m - w} - 1$，否则为 $0$。
但是这样复杂度显然是无法接受的。我们可以发现，我们这个向量集合是可能满足某些特殊性质的，经过冷静分析或者打表找规律，可以发现，对于任意一张大小为 $n$联通图来说，其线性基的大小一定为$n - 1$。感性理解一下就是，假设我们首先找到这个联通图的一个生成树，生成树上任意一条边一定是线性无关的，所以一定都在线性基中，同时对于任意一条非树边来说，其一定可以表示成路径上所有边的异或和。
同时我们还可以发现，对于任意一种方案，其合法当且仅当所有极大联通子图的黑点数量都为偶数。因为如果我们将所有黑点两两配对，一定可以在生成树上构造出一种合法的方案，即对于所有配对的路径上的边取反。
这个时候我们就可以在 $O(n+ m)$ 的时间内快速得到第一问的答案啦。接着考虑删掉一个点的情况，利用一些图论的基础知识可以发现这些也是可以快速维护的，这里不再赘述。
时间复杂度 $O(n + m)$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add (a, b)
#define cpop(a,b) a = pop (a, b)
#define cmul(a,b) a = mul (a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define bin(i) (1 << (i))
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;
inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}
int N, M;
struct edge {
int y, next;
}e[MAXN << 1];
int LINK[MAXN], len = 0, dfn[MAXN], low[MAXN], siz[MAXN], oth[MAXN], key[MAXN], ord, cnt, ban;
int cut[MAXN], deg[MAXN], vaild[MAXN], pw2[MAXN], rt[MAXN];
char s[MAXN];
inline void ins(int x, int y){
e[++len].next = LINK[x]; LINK[x] = len;
e[len].y = y; deg[x]++;
}
inline void Ins(int x, int y){
ins(x, y);
ins(y, x);
}
void DFS(int node, int fa){
dfn[node] = low[node] = ++ord;
siz[node] = key[node]; vaild[node] = 1;
rt[node] = fa ? rt[fa] : node;
Auto (i, node) if (e[i].y != fa) {
if (!dfn[e[i].y]) {
DFS(e[i].y, node);
siz[node] += siz[e[i].y];
cmin(low[node], low[e[i].y]);
if (low[e[i].y] >= dfn[node]) {
cut[node]++; vaild[node] &= (siz[e[i].y] % 2 == 0);
oth[node] += siz[e[i].y];
}
}else cmin(low[node], dfn[e[i].y]);
}
if (!fa) {
cut[node]--;
ban += siz[node] & 1;
cnt++;
}
}
int main(){
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
pw2[0] = 1;
up (i, 1, M) pw2[i] = add(pw2[i - 1], pw2[i - 1]);
up (i, 1, M) {
int x, y; scanf("%d%d", &x, &y);
Ins(x, y);
}
scanf("%s", s + 1);
up (i, 1, N) key[i] = s[i] == '1';
up (i, 1, N) if (!dfn[i]) DFS(i, 0);
printf("%d ", ban ? 0 : pw2[M - N + cnt]);
up (i, 1, N) if (vaild[i] && ban - (siz[rt[i]] & 1) == 0 && (siz[rt[i]] - oth[i] - key[i]) % 2 == 0)
printf("%d ", pw2[M - deg[i] - (N - 1) + cnt + cut[i]]);
else printf("0 ");
puts("");
up (i, 1, N) LINK[i] = key[i] = oth[i] = deg[i] = low[i] = dfn[i] = siz[i] = cut[i] = 0;
ban = ord = cnt = len = 0;
}
return 0;
}
BZOJ 5304 字串覆盖
可以发现，一个最优的方案一定是每次取最左边的合法的未被覆盖的那个位置，正确性不再证明。观察数据范围里的限制，容易发现这是一个 big & small 分开处理的题目。
首先考虑所有询问串长度 $\leq 50$ 的串：
我们将所有询问离线，扫描线从右向左，每次枚举这个位置开始的所有合法的子串，可以利用 hash + map 快速求出每个串的下一个位置，可以发现这些指向关系形成了一棵树。那么我们建出这棵树，最后 DFS 整棵树，对于所有询问离线后在树上倍增即可。
然后考虑剩下的询问，可以发现暴力维护即可，但是要解决的问题就是如何快速找到每个位置的下一个合法子串。这是一个经典问题，我们把两个串建出广义 SAM，在 Parent 树上用线段树维护第一个串的所有出现位置，线段树合并可以方便的转移到父亲，对于每个询问的子串在 Parent 树上倍增求出那个合法的节点即可。
这个看起来非常莽的做法如果随机数据其实不一定跑得过暴力，但是出题人可以限制了询问串的长度，所以我们只分析极限数据情况下的复杂度。首先对于 $len \leq 50$ 的，预处理的复杂度为 $50n \log Q$，对于 $2001 \leq len$，我们利用 SAM 暴力计算，复杂度为 $Q \frac{n} {len} \log n$，对于 $51 \leq len \leq 2000$ 的，因为保证了询问数不超过 $q = 11000$ 个，同时保证了均匀随机，所以可以认为 $len = 1000$，所以复杂度为 $q \frac{n}{ len} \log n$。
真是 sxbk
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ull unsigned long long
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add (a, b)
#define cpop(a,b) a = pop (a, b)
#define cmul(a,b) a = mul (a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define pw(i) (1 << (i))
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
const int MAXN = 4e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXS = MAXN * 10;
const int oo = 0x3f3f3f3f;
const int L = 40;
const int MAXL = L + 1;
const ull bs = 171717;
map<ull, int> w;
int N, Q, K, qrys, g[MAXM][MAXL], ID[MAXM][MAXL];
char s[MAXN];
struct Query {
int le, ri, cl, cr, o, v;
inline Query (int le = 0, int ri = 0, int cl = 0, int cr = 0, int o = 0, int v = 0) : le(le), ri(ri), cl(cl), cr(cr), o(o), v(v) {}
inline bool operator < (const Query & v) const { return le > v.le; }
}qry[MAXN];
ull hs[MAXN], ht[MAXN], bin[MAXN];
inline ull get(ull *h, int le, int ri) { return h[ri] - h[le - 1] * bin[ri - le + 1]; }
ll ans[MAXN];
int p, q, np, nq, now = 1, rt = 1, cnt = 1;
int pre[MAXN][21], step[MAXN], son[MAXN][26], pos[MAXN];
struct tree {
int son[2], siz;
}t[MAXN * 30];
int root[MAXN], seg_cnt;
inline int NewNode(int s0, int s1, int siz){
int k = ++seg_cnt;
t[k].son[0] = s0; t[k].son[1] = s1; t[k].siz = siz;
return k;
}
void ins(int le, int ri, int &k, int o){
k = NewNode(t[k].son[0], t[k].son[1], t[k].siz + 1);
if (le == ri) return;
int mi = (le + ri) >> 1;
o <= mi ? ins(le, mi, t[k].son[0], o) : ins(mi + 1, ri, t[k].son[1], o);
}
void Merge(int le, int ri, int &k, int x){
if (!k || !x) return (void)(k += x);
int mi = (le + ri) >> 1;
k = NewNode(t[k].son[0], t[k].son[1], t[k].siz + t[x].siz);
Merge(le, mi, t[k].son[0], t[x].son[0]);
Merge(mi + 1, ri, t[k].son[1], t[x].son[1]);
}
int getcl(int le, int ri, int k, int o){
if (!t[k].siz || o > N) return oo;
if (le == ri) return o <= le ? le : oo;
int s0 = t[k].son[0], s1 = t[k].son[1], mi = (le + ri) >> 1;
if (o <= le && t[s0].siz) return getcl(le, mi, s0, o);
else if (o <= mi && t[s0].siz) {
int x = getcl(le, mi, s0, o);
if (x == oo) return getcl(mi + 1, ri, s1, o);
return x;
}else return getcl(mi + 1, ri, s1, o);
}
int extend(int nxt, int o){
p = now;
if (son[p][nxt]) {
q = son[p][nxt];
if (step[q] == step[p] + 1) return now = q;
else {
step[nq = ++cnt] = step[p] + 1;
memcpy(son[nq], son[q], sizeof(son[q]));
pre[nq][0] = pre[q][0];
pre[q][0] = nq;
for (; son[p][nxt] == q; p = pre[p][0]) son[p][nxt] = nq;
return now = nq;
}
}else {
step[np = now = ++cnt] = step[p] + 1;
if (o) ins(1, N, root[np], o);
for (; p && !son[p][nxt]; p = pre[p][0]) son[p][nxt] = np;
if (!p) pre[np][0] = rt;
else {
q = son[p][nxt];
if (step[q] == step[p] + 1) pre[np][0] = q;
else {
step[nq = ++cnt] = step[p] + 1;
memcpy(son[nq], son[q], sizeof(son[q]));
pre[nq][0] = pre[q][0];
pre[np][0] = pre[q][0] = nq;
for (; son[p][nxt] == q; p = pre[p][0]) son[p][nxt] = nq;
}
}
return now;
}
}
int pool[MAXN], ord[MAXN];
inline int getanc(int le, int ri){
int len = ri - le + 1, x = pos[ri];
down (i, 20, 0) while (step[pre[x][i]] >= len) x = pre[x][i];
return x;
}
int tree_cnt;
struct edge {
int y, next;
}e[MAXS];
int LINK[MAXS], len = 0;
inline void ins(int x, int y){
e[++len].next = LINK[x]; LINK[x] = len;
e[len].y = y;
}
vector<int> ss[MAXS];
int dep[MAXS], D[MAXN];
ll sum[MAXN];
void DFS(int node, int d){
D[d] = node;
up (i, 0, SZ(ss[node]) - 1) {
int o = ss[node][i], le = qry[o].le, ri = qry[o].ri, len = qry[o].cr - qry[o].cl + 1;
ri = ri - len + 1;
ll tmp = 0; int x = d;
down (j, 20, 0) if (x >= pw(j) && dep[D[x - pw(j)]] <= ri) {
tmp += sum[x] - sum[x - pw(j)];
x -= pw(j);
}
if (dep[D[x]] <= ri) tmp += sum[x] - sum[x - 1];
ans[qry[o].o] = tmp;
}
Auto (i, node) {
sum[d + 1] = sum[d] + K - dep[e[i].y];
DFS(e[i].y, d + 1);
}
}
int main(){
scanf("%d%d", &N, &K);
bin[0] = 1;
up (i, 1, N) bin[i] = bin[i - 1] * bs;
scanf("%s", s + 1);
up (i, 1, N) extend(s[i] - 'a', i);
up (i, 1, N) hs[i] = hs[i - 1] * bs + s[i];
scanf("%s", s + 1); now = rt;
up (i, 1, N) pos[i] = extend(s[i] - 'a', 0);
up (i, 1, N) ht[i] = ht[i - 1] * bs + s[i];
up (i, 1, cnt) pool[step[i]]++;
up (i, 1, N) pool[i] += pool[i - 1];
down (i, cnt, 1) ord[pool[step[i]]--] = i;
down (i, cnt, 1) {
int o = ord[i];
Merge(1, N, root[pre[o][0]], root[o]);
}
up (j, 1, 20) up (i, 1, cnt) pre[i][j] = pre[pre[i][j - 1]][j - 1];
scanf("%d", &Q);
up (i, 1, Q) {
int le, ri, cl, cr; scanf("%d%d%d%d", &le, &ri, &cl, &cr);
int len = cr - cl + 1;
if (len <= L && le + len - 1 <= ri) qry[++qrys] = Query(le, ri, cl, cr, i, 0);
else {
int x = getanc(cl, cr), len = cr - cl + 1;
int cur = getcl(1, N, root[x], le + len - 1);
while (cur <= ri) {
ans[i] += K - (cur - len + 1);
cur = getcl(1, N, root[x], cur + len);
}
}
}
sort(qry + 1, qry + qrys + 1);
up (i, 1, qrys) w[get(ht, qry[i].cl, qry[i].cr)] = N + 1;
up (i, 1, L) g[N + 1][i] = N + 1;
int cur = N + 1;
up (i, 1, qrys) {
while (qry[i].le < cur) {
cur--; int m = min(L, N - cur + 1);
up (j, 1, m) if (w[get(hs, cur, cur + j - 1)]) {
ull h = get(hs, cur, cur + j - 1);
ID[cur][j] = ++tree_cnt; dep[tree_cnt] = cur;
int nxt = w[h]; g[cur][j] = nxt;
while (nxt <= cur + j - 1) nxt = g[nxt][j];
ins(ID[nxt][j], ID[cur][j]);
// printf("%d -> %d ", cur, nxt);
w[h] = cur;
}
}
ull h = get(ht, qry[i].cl, qry[i].cr);
int len = qry[i].cr - qry[i].cl + 1, st = w[h];
if (st + len - 1 > qry[i].ri) continue;
qry[i].v = ID[st][len];
ss[qry[i].v].push_back(i);
}
dep[0] = oo;
DFS(0, 0);
up (i, 1, Q) printf("%lld\n", ans[i]);
return 0;
}
BZOJ 5305 苹果树
首先容易发现，对于一个大小为 $n$ 的二叉树来说，方案数为 $n!$，因为是所有路径的距离和，经典套路转化成每条边的贡献。为了方便 DP，我们定义 $f(n)$ 表示大小为 $n$ 的树的答案，同时定义 $g(n)$ 表示大小为 $n$ 的树的所有方案的所有节点到根的路径距离之和的和。
首先我们 DP 出来 $g(n)$，然后根据 $g(n)$ 就可以很方便的 DP 出 $f(n)$，因为要写一大堆组合数这里就不说啦，自己 YY 吧。
因为题目范围里有关于 $P$ 是否是质数的限制，搞得考场上意识模糊的我差点以为中间的阶乘还要上 CRT，还好冷静想了才想发现是否是质数没啥影响。
时间复杂度 $O(n^2)$。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add(a, b)
#define cpop(a,b) a = pop(a, b)
#define cmul(a,b) a = mul(a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define bin(i) (1 << (i))
#define SZ(x) (int)x.size()
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }
const int MAXN = 2005;
int mod;
inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}
int qpow(int a, int b){
int c = 1;
while (b) {
if (b & 1) cmul(c, a);
cmul(a, a); b >>= 1;
}
return c;
}
int N, fac[MAXN], C[MAXN][MAXN], f[MAXN], g[MAXN];
int main(){
scanf("%d%d", &N, &mod);
fac[0] = 1;
up (i, 1, N) fac[i] = mul(fac[i - 1], i);
up (i, 0, N) {
C[i][0] = 1;
up (j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
}
up (i, 1, N) {
up (j, 0, i - 1) {
int x = j, y = i - j - 1, sum = 0;
cadd(sum, mul(add(g[x], mul(fac[x], x)), mul(fac[y], C[x + y][y])));
cadd(sum, mul(add(g[y], mul(fac[y], y)), mul(fac[x], C[x + y][x])));
cadd(g[i], sum);
}
}
up (i, 1, N) {
up (j, 0, i - 1) {
int x = j, y = i - j - 1, sum = 0;
cadd(sum, mul(add(g[x], mul(fac[x], x)), mul(mul(C[x + y][y], fac[y]), y + 1)));
cadd(sum, mul(add(g[y], mul(fac[y], y)), mul(mul(C[x + y][x], fac[x]), x + 1)));
cadd(sum, mul(f[x], mul(C[x + y][y], fac[y])));
cadd(sum, mul(f[y], mul(C[x + y][x], fac[x])));
cadd(f[i], sum);
}
}
printf("%d\n", f[N]);
return 0;
}
BZOJ 5306 染色
容易发现这是一个容斥的题目，然后我们脑补一下可以写出容斥的式子，由于本垃圾懒癌晚期实在不想写那一大堆 LaTex 了，所以你们自己脑补吧。
然后我们可以发现容斥的式子本质上是一个卷积的形式，NTT 一下就行啦。
复杂度 $O(n + m\log m )$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add(a, b)
#define cpop(a,b) a = pop(a, b)
#define cmul(a,b) a = mul(a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define bin(i) (1 << (i))
#define SZ(x) (int)x.size()
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }
const int mod = 1004535809;
const int oo = 0x3f3f3f3f;
const int L = 1e7;
const int MAXM = L + 5;
const int MAXN = 4e5 + 5;
inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}
int qpow(int a, int b){
int c = 1;
while (b) {
if (b & 1) cmul(c, a);
cmul(a, a); b >>= 1;
}
return c;
}
int fac[MAXM], invfac[MAXM];
inline int C(int a, int b){
if (a < 0 || b < 0 || a < b) return 0;
return mul(fac[a], mul(invfac[b], invfac[a - b]));
}
int N, M, S, f[MAXN], W[MAXN];
int pos[MAXN], omega[MAXN], inv[MAXN], A[MAXN], B[MAXN];
void FFT(int n, int *a, bool idft){
up (i, 0, n - 1) if (pos[i] < i) swap(a[pos[i]], a[i]);
int *w = idft ? inv : omega;
for (int len = 2; len <= n; len <<= 1) {
int m = len >> 1;
for (int j = 0; j < n; j += len) up (k, 0, m - 1) {
int z = mul(a[j + m + k], w[n / len * k]);
a[j + m + k] = pop(a[j + k], z);
a[j + k] = add(a[j + k], z);
}
}
if (idft) {
int x = qpow(n, mod - 2);
up (i, 0, n - 1) cmul(a[i], x);
}
}
int main(){
fac[0] = invfac[0] = invfac[1] = 1;
up (i, 1, L) fac[i] = mul(i, fac[i - 1]);
up (i, 2, L) invfac[i] = mul(mod - mod / i, invfac[mod % i]);
up (i, 1, L) cmul(invfac[i], invfac[i - 1]);
scanf("%d%d%d", &N, &M, &S);
up (i, 0, M) scanf("%d", &W[i]);
int cur = 1, n = N;
f[0] = qpow(M, N);
up (i, 1, M) {
if (n < S) break;
cmul(cur, C(n, S));
n -= S;
f[i] = mul(cur, mul(C(M, i), qpow(M - i, n)));
}
n = 1;
while (n <= M + M) n <<= 1;
up (i, 0, n - 1) {
pos[i] = pos[i >> 1] >> 1;
if (i & 1) pos[i] |= n >> 1;
}
int x = qpow(3, (mod - 1) / n), y = qpow(x, mod - 2);
omega[0] = inv[0] = 1;
up (i, 1, n - 1) {
omega[i] = mul(omega[i - 1], x);
inv[i] = mul(inv[i - 1], y);
}
up (i, 0, M) A[i] = mul(f[M - i], fac[M - i]);
up (i, 0, M) {
int sum = (i & 1) ? (mod - 1) : 1;
B[i] = mul(sum, invfac[i]);
}
FFT(n, A, 0); FFT(n, B, 0);
up (i, 0, n - 1) cmul(A[i], B[i]);
FFT(n, A, 1);
int ans = 0;
up (i, 0, M) {
int x = A[M - i];
cmul(x, invfac[i]);
cadd(ans, mul(x, W[i]));
}
printf("%d\n", ans);
return 0;
}