#P6911. 数列

    ID: 6742 传统题 3000ms 512MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-递归拆解依赖莫比乌斯反演倍数枚举行列式

数列

题目描述

定义两个从下标 11 开始的无限数列 A,BA,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}$$

给定 nn 和函数 FF 在 1,…,n1,\ldots,n 上的取值。构造 n×nn\times n 矩阵 CC,其中

Ci,j=BF(gcd⁡(i,j)).C_{i,j}=B_{F(\gcd(i,j))}.

求 det⁡C\det C 对 998244353998244353 取模的结果。

输入格式

第一行一个整数 nn。第二行 nn 个整数,第 ii 个为 F(i)F(i)。

输出格式

输出一行一个整数,表示行列式对 998244353998244353 取模后的非负余数。

样例

1
1
1

矩阵为 [1][1],行列式为 11。

数据范围

1≤n≤2×1051\le n\le2\times10^5,1≤F(i)≤10181\le F(i)\le10^{18}。原题时间限制 11 秒,内存限制 512512 MB。

子任务 分值 附加限制
1 n≤10n\le10,F(i)≤105F(i)\le10^5
2 12 n≤200n\le200,F(i)≤106F(i)\le10^6
3 27 F(i)≤106F(i)\le10^6
4 n≤200n\le200
5 33 无

原 PDF 题面