花了几分钟时间学单位根反演 /cy /cy /cy
对没错我就是打算先做 HNOI2019 D2T2 再做 D2T1（
考虑求 \(\sum\limits_{i=0}^4 a_i c_i\)，其中 \[ c_i = \sum\limits_{j=0}^n \binom nj s^j [j \equiv i \pmod 4] \]
那么设个 \[ f(x) = \sum\limits_{i=0}^n \binom ni s^i = (sx + 1)^n \]
然后套单位根反演有 \[ \begin{aligned} c_{4-i} &= \sum\limits_{j=i}^{n+i} \binom n{j-i} s^{j-i} [4 \mid j] \\ &= \frac 14 \sum\limits_{j=0}^3 f(\omega_4^j) \omega_4^{ij} \\ &= \frac 14 \sum\limits_{j=0}^3 (s\omega_4^j + 1)^n \omega_4^{ij} \end{aligned} \]
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const int mod = 998244353;
const int inv = 748683265;
const int G = 3;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int T;
long long n;
int s,a[4],rt[4],ans;
int main()
{
for(register int i = 0;i < 4;++i)
rt[i] = fpow(G,(mod - 1) / 4 * i);
scanf("%d",&T);
for(;T;--T)
{
scanf("%lld%d%d%d%d%d",&n,&s,a,a + 1,a + 2,a + 3),n %= (mod - 1),ans = 0;
for(register int i = 0,c;i < 4;++i)
{
c = 0;
for(register int j = 0;j < 4;++j)
c = (c + (long long)fpow(((long long)s * rt[j] + 1) % mod,n) * rt[j * (4 - i) % 4]) % mod;
c = (long long)c * inv % mod,
ans = (ans + (long long)c * a[i]) % mod;
}
printf("%d\n",ans);
}
}