E2-C 杀戮尖塔

题目描述

BellalabellaBellalabella 喜欢玩一个叫做杀戮尖塔的游戏。游戏一共有 nn 层，每层有 kk 个关卡，编号为 1,2,…,k1,2,…,k。玩家每通过一关，则可以进入下一层 kk 个关卡中任意一个。当通过 nn 层时则会抵达 BossBoss 房挑战最终 BossBoss。

BellalabellaBellalabella 觉得这个这个游戏太简单了，因此她给自己设置了两个 debuffdebuff：

  • 相邻两层不能挑战编号相同的关卡，即如果进入了第$ i（1≤i<n）$层的第 j（1≤j≤k）j（1≤j≤k）关，则不可进入第 i+1i+1 层的第 jj 关。

  • 共有 mm 层被设置了陷阱，层数分别为 a1,a2,…,ama_1,a_2,…,a_m，被设置陷阱的层不可进入第 kk 关，即仅可以进入第 1,2,…,k−11,2,…,k−1 关。

请问在 debuffdebuff 的影响下，BellalabellaBellalabella 一共有多少条不同的路线能够抵达 BossBoss 房。两条路线不同当且仅当存在一层两条路线所挑战的关卡不同。

由于答案可能很大，你只需要输出答案对 998244353998244353 取模后的结果。

输入格式

第一行三个整数 n,m,k（1≤n≤106，0≤m≤n，2≤k≤109）n,m,k（1≤n≤10^6，0≤m≤n，2≤k≤10^9），含义同题目描述。

第二行 mm 个互不相同的正整数 a1,a2,…,am（1≤ai≤n）a_1,a_2,…,a_m（1≤a_i≤n），含义同题目描述。

输出格式

一行一个非负整数，表示不同路线数对 998244353998244353 取模后的结果。

输入样例 1

1
2
3 1 2
2

输出样例 1

1
1

输入样例 2

1
2
4 2 3
2 3

输出样例 2

1
8

输入样例 3

1
4 0 3

输出样例 3

1
24

题目分析

对于每层它要么可以进入kk间，要么不能进入。所以可以分开计算两种情况，dp[i][0]dp[i][0]表示在第ii层不选择进入第kk间时的总方案数，dp[i][1]dp[i][1]表示在第ii层选择第kk间时的方案数。

如果第ii层有陷阱很容易得到dp[i][1]=0dp[i][1]=0，如果没有陷阱则有：dp[i][1]=dp[i−1][0]dp[i][1]=dp[i-1][0]，无论有没有陷阱都有dp[i][0]=dp[i−1][0]∗(k−2)+dp[i−1][k]∗(k−1)dp[i][0]=dp[i-1][0]*(k-2)+dp[i-1][k]*(k-1)。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#define MOD 998244353
using namespace std;
bool a[1000005];
int dp[1000005][2];
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        a[x] = true;
    }

    if (a[1])
    {
        dp[1][1] = 0;
        dp[1][0] = k - 1;
    }
    else
    {
        dp[1][1] = 1;
        dp[1][0] = k - 1;
    }
    for (int i = 2; i <= n; i++)
    {
        if (a[i])
        {
            dp[i][1] = 0;
        }
        else
        {
            dp[i][1] = dp[i - 1][0];
        }
        dp[i][0] = ((dp[i - 1][0] * (k - 2) % MOD * 1LL) % MOD + (dp[i - 1][1] * (k - 1) % MOD * 1LL) % MOD) % MOD;
    }
    cout << (dp[n][0] + dp[n][1]) % MOD;
    return 0;
}