毒瘤交互。
题目大意
有$N$个盒子，第$i$个盒子里面有$p_i$个球，从一个盒子中只能拿一个球出来。求恰好拿出来$M$个球的方案数，对$998244353$取模。
你不知道$pi$的具体的值，只能指定操作。
具体来说，你有一个长度为$T$的整型数组$A$，其中前$N$个位置初始存的是$p_1,p_2,⋯,p_N$。其余位置的初始值由你通过Set操作来决定。
在决定完初始值之后，你就只能指定操作了。你只能提出：
- $A_i=A_j+A_k$
- $A_i=A_j−A_k$
- $A_i=A_j\times A_k$（所有运算均在模$998244353$意义下）
- 过程中不允许你修改前$N$个位置的值。
- 过程中不允许使用
Set操作赋值。
你还需要指出$A$中的哪一个数是答案。
数据范围
$1\le M\le N\le 1000,T=1004$
解析
由生成函数，答案显然为：
$$
Ans=\prod_{i=1}^n (1+p_i\times x) [x^{n-m}]
$$
然后我们考虑一些事情：
操作的处理
归零
直接把一个数减去自身即可。
归一
费马小定理即可。
$$
a^{P-1}\equiv1(\bmod P)
$$
复制
先归零，然后加起来即可。
（计算中）赋值
在计算前，先搞一个$1$出来。
把要赋的值二进制分解赋值即可。
优化
直接搞暴力复杂度有点爆炸。
考虑一下$IDFT$的过程，那么我们可以把答案化成这样的形式：
$$
Ans=\frac{1}{N}\times\sum_{i=0}^{N-1}f(\omega_N^i)\times\omega_N^{-i\times m}
$$
这个时候我们就发现$T=1004$给我们剩下了哪$4$个变量了：
$$
Ans,f(x),x,y=1
$$
实现时预处理出$\omega_N^i$即可。
Notice
哎呀这个东西时真的坑。
我被我的巨大常数送走无数次之后，决心：
让常数优化成为习惯。
然后我就疯狂加inline，然后就疯狂Complie Error。
调了好久，最后原因是交互库你里面的函数没有inline，而我加了。
这样会导致什么呢？对，交互库的函数就没有定义了。
而且这个东西不用g++ -o %< % grader.cpp还查不出来。
难受😔。
Code
1 | #define REP(i, s, e) for (int i = s; i <= e; i++) |