「HAOI 2018」「BZOJ 5302 - 5306」题解

出题人的题解

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