A6662 | 「雅礼集训 2018 Day4」Magic
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
> 前进！前进！不择手段地前进！——托马斯 · 维德
魔法纪元元年。
1453 年 5 月 3 日 16 时，高维碎片接触地球。
1453 年 5 月 28 日 21 时，碎片完全离开地球。
1453 年，君士坦丁堡被围城，迪奥娜拉接触到四维泡沫空间，成为魔法师，最终因高维碎片消失失去魔力而身死。
为了改写这段历史，你不惜耗费你珍藏已久的魔术卡来回到魔法纪元元年。
在使用这些魔术卡之前，你却对它们的排列起了兴趣...
桌面上摆放着 $m$ 种魔术卡，共 $n$ 张，第 $i$ 种魔术卡数量为 $a_i$，魔术卡顺次摆放，形成一个长度为 $n$ 的魔术序列，在魔术序列中，若两张相邻魔术卡的种类相同，则它们被称为一个魔术对。
两个魔术序列本质不同，当且仅当存在至少一个位置，使得两个魔术序列这个位置上的魔术卡的种类不同，求本质不同的恰好包含 $k$ 个魔术对的魔术序列的数量，答案对 $998244353$ 取模。
魔法纪元元年。
1453 年 5 月 3 日 16 时，高维碎片接触地球。
1453 年 5 月 28 日 21 时，碎片完全离开地球。
1453 年，君士坦丁堡被围城，迪奥娜拉接触到四维泡沫空间，成为魔法师，最终因高维碎片消失失去魔力而身死。
为了改写这段历史，你不惜耗费你珍藏已久的魔术卡来回到魔法纪元元年。
在使用这些魔术卡之前，你却对它们的排列起了兴趣...
桌面上摆放着 $m$ 种魔术卡，共 $n$ 张，第 $i$ 种魔术卡数量为 $a_i$，魔术卡顺次摆放，形成一个长度为 $n$ 的魔术序列，在魔术序列中，若两张相邻魔术卡的种类相同，则它们被称为一个魔术对。
两个魔术序列本质不同，当且仅当存在至少一个位置，使得两个魔术序列这个位置上的魔术卡的种类不同，求本质不同的恰好包含 $k$ 个魔术对的魔术序列的数量，答案对 $998244353$ 取模。
输入格式
第一行三个整数 $m, n, k$。
第二行 $m$ 个正整数，第 $i$ 个正整数表示 $a_i$。
第二行 $m$ 个正整数，第 $i$ 个正整数表示 $a_i$。
输出格式
一行一个整数表示答案。
输入输出样例
输入 #1
3 5 1 2 2 1
输出 #1
12
输入 #2
3 6 0 1 2 3
输出 #2
10
输入 #3
2 100 20 50 50
输出 #3
164333748
输入 #4
5 2333 666 300 1000 233 200 600
输出 #4
119409616
输入 #5
5 30000 0 4000 5000 6000 7000 8000
输出 #5
522962185
输入 #6
6 50000 12345 9896 104 15000 13000 8000 4000
输出 #6
940147981
| 测试点编号 | $m$ | $n$ | $k$ | 特殊性质 |
| :-: | :-: | :-: | :-: | :-: |
| 1 | $=2$ | $\leq 300$ | $ = 1$ | |
| 2 | $=2$ | $\leq 300$ | $ = 2$ | |
| 3 | $=2$ | $\leq 300$ | | |
| 4 | $=2$ | $\leq 300$ | | |
| 5 | $=3$ | $\leq 16$ | | |
| 6 | $=3$ | $\leq 16$ | | |
| 7 | $=3$ | $\leq 80$ | | |
| 8 | $=3$ | $\leq 80$ | | |
| 9 | $=3$ | $\leq 80$ | | |
| 10 | $ \leq 100$ | $\leq 100$ | $= 0$ | $m = n$ |
| 11 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 12 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 13 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 14 | $ \leq 2000$ | $\leq 5000$ | | |
| 15 | $ \leq 2000$ | $\leq 5000$ | | |
| 16 | $ \leq 2000$ | $\leq 5000$ | | |
| 17 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 18 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 19 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 20 | $ \leq 20000$ | $\leq 100000$ | $= 0$| |
| 21 | $ \leq 20000$ | $\leq 100000$ | $= 0$| |
| 22 | $ \leq 20000$ | $\leq 100000$ | | |
| 23 | $ \leq 20000$ | $\leq 100000$ | | |
| 24 | $ \leq 20000$ | $\leq 100000$ | | |
| 25 | $ \leq 20000$ | $\leq 100000$ | | | |
对于 $100 \%$ 的数据满足 $1 \leq m \leq 20000, 0 \leq k \leq n \leq 100000, \sum_{i = 1}^{m} a_i = n$。
| :-: | :-: | :-: | :-: | :-: |
| 1 | $=2$ | $\leq 300$ | $ = 1$ | |
| 2 | $=2$ | $\leq 300$ | $ = 2$ | |
| 3 | $=2$ | $\leq 300$ | | |
| 4 | $=2$ | $\leq 300$ | | |
| 5 | $=3$ | $\leq 16$ | | |
| 6 | $=3$ | $\leq 16$ | | |
| 7 | $=3$ | $\leq 80$ | | |
| 8 | $=3$ | $\leq 80$ | | |
| 9 | $=3$ | $\leq 80$ | | |
| 10 | $ \leq 100$ | $\leq 100$ | $= 0$ | $m = n$ |
| 11 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 12 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 13 | $ \leq 2000$ | $\leq 5000$ | $= 0$ | |
| 14 | $ \leq 2000$ | $\leq 5000$ | | |
| 15 | $ \leq 2000$ | $\leq 5000$ | | |
| 16 | $ \leq 2000$ | $\leq 5000$ | | |
| 17 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 18 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 19 | $ \leq 20000$ | $\leq 100000$ | $= 0$|$a_i$均相等且 $\leq 20$ |
| 20 | $ \leq 20000$ | $\leq 100000$ | $= 0$| |
| 21 | $ \leq 20000$ | $\leq 100000$ | $= 0$| |
| 22 | $ \leq 20000$ | $\leq 100000$ | | |
| 23 | $ \leq 20000$ | $\leq 100000$ | | |
| 24 | $ \leq 20000$ | $\leq 100000$ | | |
| 25 | $ \leq 20000$ | $\leq 100000$ | | | |
对于 $100 \%$ 的数据满足 $1 \leq m \leq 20000, 0 \leq k \leq n \leq 100000, \sum_{i = 1}^{m} a_i = n$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？