#P6229. Nishikata

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

Nishikata

题目描述

给你一个 nnmm 列的方阵,你有 1n1\sim nnn 个数各 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