题目描述
定义两个从下标 1 开始的无限数列 A,B。
$$\begin{aligned}
A_1&=1,\\
A_{2k}&=-A_k &&(k\ge1),\\
A_{2k-1}&=(-1)^{k-1}A_k &&(k>1),\\
B_1&=1,\\
B_k&=B_{k-1}+A_k &&(k>1).
\end{aligned}$$
给定 n 和函数 F 在 1,…,n 上的取值。构造 n×n 矩阵 C,其中
Ci,j=BF(gcd(i,j)).
求 detC 对 998244353 取模的结果。
输入格式
第一行一个整数 n。第二行 n 个整数,第 i 个为 F(i)。
输出格式
输出一行一个整数,表示行列式对 998244353 取模后的非负余数。
样例
1
1
1
矩阵为 [1],行列式为 1。
数据范围
1≤n≤2×105,1≤F(i)≤1018。原题时间限制 1 秒,内存限制 512 MB。
| 子任务 |
分值 |
附加限制 |
| 1 |
n≤10,F(i)≤105 |
| 2 |
12 |
n≤200,F(i)≤106 |
| 3 |
27 |
F(i)≤106 |
| 4 |
n≤200 |
| 5 |
33 |
无 |
原 PDF 题面