#P3860. Permanent

    ID: 3063 传统题 2000ms 64MiB 尝试: 118 已通过: 20 难度: 8 上传者: 标签>CF2500提高+/省选-普通生成函数容斥原理卷积转化分治乘积NTT阶乘逆元预处理By镇海中学

Permanent

题目描述

给出 nn 个整数 a1,…,ana_1,\dots,a_n。对每个 i=1,…,mi=1,\dots,m,构造一个 (n+i−1)×(n+i−1)(n+i-1)\times(n+i-1) 的方阵 W(i)W^{(i)},其元素为

$$W^{(i)}_{x,y}=\begin{cases} a_x & x=y\le n,\\ 0 & x=y>n,\\ 1 & x\ne y. \end{cases}$$

求这些矩阵的积和式。一个 s×ss\times s 矩阵 WW 的积和式为 ∑π∏x=1sWx,π(x)\displaystyle\sum_{\pi}\prod_{x=1}^s W_{x,\pi(x)},其中 π\pi 遍历 1,…,s1,\dots,s 的所有排列。答案对 998244353998244353 取模。

输入格式

输入包含多组数据。每组第一行两个整数 n,mn,m(1≤n,m≤1051\le n,m\le10^5),第二行 nn 个整数 a1,…,ana_1,\dots,a_n(0≤ai≤1060\le a_i\le10^6)。读到 0 0 时结束。

输出格式

对第 kk 组数据先输出一行 Case #k:。组号从 11 开始。随后输出 mm 行,第 ii 行给出矩阵 W(i)W^{(i)} 的积和式对模数取模的值。

样例

3 2
2 3 3
0 0
Case #1:
28
46

原 BZOJ 题面存档及矩阵定义