Wannafly Winter Camp 2020 Day 6A Convolution - NTT
2024-09-06 12:36:42
求 \(\sum_{i=1}^n \sum_{j=1}^n 2^{a_ia_j}\)
Solution
化简一下
\[
2^{a_ia_j} = p^{(a_i+a_j)^2-a_i^2-a_j^2}, \ p^2= 2(\bmod 998244353)
\]
这个 \(p\) 我们可以预先暴力找到它 \(=116195171\),计算答案
\[
\begin{align}
&\sum_i \sum_j p^{(a_i+a_j)^2-a_i^2-a_j^2}
\\
=& \sum_kp^{k^2} \sum_{a_i+a_j=k}p^{-a_i^2}p^{-a_j^2}
\end{align}
\]
设 \(f(x)=\sum_i p^{-a_i^2}x^{a_i}\),则答案即为
\[
\sum_k p^{k^2}[x^k]f^2(x)
\]
用 NTT 计算即可
最新文章
- 你真的会玩SQL吗?EXISTS和IN之间的区别
- 【luogu】 P1433 吃奶酪
- Java关键字用法及区别
- java 15 - 6 List的方法
- POJ 1191 棋盘分割(DP)
- 倒数计数器-CountDownLatch
- 找出Active Directory架构操作主机方法!
- android-'Using 1.7 requires compiling with Android 4.4 (KitKat); currently using API 8'
- sublime text There are no packages 解决!
- How to Build CyanogenMod for One X (codename: endeavoru)
- Apache httpd.conf配置详解
- java八大基本数据类型
- 【English】四、Y结尾名词变复数
- ApiUser
- 炫酷MD风之dialog各种对话框
- 一套简单的git版本控制代码
- .net core 中使用ef 访问mysql
- C# 一般处理程序下载文件
- 前端 HTML标签属性
- 以ORM的思路来从Excel文件中读取JSON数据列表