6997：愿望幽灵

题目描述

给定 $c$，设 $q_k$ 表示有一个 $2\times k$ 的矩阵，初始时所有位置均为空，要从中选出 $k$ 个位置涂上 $0,1,\dots,c$ 的数字，使得每列至多存在一个数字非 $0$ 的方案数。

每个位置只能涂上一种数字。

空的位置与染上任何一个数字的位置都是不同的。

每种数字可以出现在多个位置上。

给定 $n$，求 $q_1,q_2,\dots,q_n$ 模 $998244353$。

为了减小输出量，只需要输出它们的异或和即可。

输入解释

本题有多组测试数据。

第一行，一个正整数 $T$ $(1 \le T \le 5)$ 表示数据组数。

对于每组数据，第一行两个整数 $n,c$ $(1 \le n \le 10^7,0 \le c < 998244353)$。

输出解释

对于每组数据，一行一个非负整数，表示 $q_1,q_2,\dots,q_n$ 模 $998244353$ 后的异或和。

输入样例

输出样例

170
154
420

来自杭电HDUOJ的附加信息

Hint

对于第一组数据：异或前的结果为 [2, 6, 20, 70, 252]。对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 即可。对 q[2]，考虑任意选出两个格子涂上 0 即可。对于第二组数据：异或前的结果为 [4, 22, 136]。对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 或 1 即可。对于第三组数据：异或前的结果为 [6, 46, 396]。

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2021 年百度之星·程序设计大赛 - 初赛一

源链接： HDU-6997

最后修改于 2021-10-23T19:10:59+00:00 由爬虫自动更新

共提交 3 次

通过率 0.0%

时间上限	内存上限
4000/2000MS(Java/Others)	262144/262144K(Java/Others)