#P6229. Nishikata

    ID: 5519 传统题 8000ms 512MiB 尝试: 7 已通过: 1 难度: 9 上传者: 标签>CF2700组合数学生成函数FFT分治数学多项式倍增

Nishikata

题目描述

给你一个 nn 行 mm 列的方阵,你有 1∼n1\sim n 这 nn 个数各 mm 个,要放进方阵中使得数 ii 不在第 ii 行,令方案数为 F(n,m)F(n,m)。

求 $\displaystyle \bigoplus _{i=1}^{n} (F(i,m)\bmod 998244353)$。

输入格式

一行两个正整数 n,mn,m。

输出格式

一行一个整数表示答案。

3 2
11

数据范围与提示

子任务编号 分值 nmnm 特殊性质
1 1010 10610^6 m=1m=1
2 1010 ≤5000\leq 5000 无
3 4040 ≤105\leq 10^5
5 4040 ≤106\leq 10^6