题意

给定整数 $s,t,u$，已知复数 $a,b,c$ 满足下列式子

  • $a+b+c=s$
  • $ab+bc+ca=t$
  • $abc=u$

求 $\dfrac{a^n\left(b^m-c^m\right)+b^n\left(c^m-a^m\right)+c^n\left(a^m-b^m\right)}{\left(a-b\right)\left(b-c\right)\left(c-a\right)}\bmod 998244353$ ，其中 $0\le s,t,u<998244353,1\le n,m\le 10^{18}$

分析

考虑找出$f_{n,m}=\sum_{cyc}\left(a^nb^m-a^mb^n\right)$ 的递推式

$$ \begin{aligned} f_{n,m}=&\sum_{cyc}\left(a^nb^m-a^mb^n\right) \\ =&\sum_{cyc}ab\sum_{cyc}\left(a^{n-1}b^{m-1}-a^{m-1}b^{n-1}\right)-\sum_{cyc}\left(ab^{n}c^{m-1}-ab^{m}c^{n-1}+a^{m}bc^{n-1}-a^{n}bc^{m-1}\right)\\ =&\left(\sum_{cyc}ab\right)\cdot f_{n-1,m-1}-abc\left(f_{n-2,m-1}+f_{n-1,m-2}\right) \\ f_{n-2,m-1}+f_{n-1,m-2}=&\sum_{cyc}\left(a+b\right)\sum_{cyc}\left(a^{n-2}b^{m-2}-a^{m-2}b^{n-2}\right)\\&-\sum_{cyc}\left(ab^{n-2}c^{m-2}-ab^{m-2}c^{n-2}+b^{n-1}c^{m-2}-b^{m-1}c^{n-2}+a^{m-1}c^{n-2}-a^{n-1}c^{m-2}+a^{m-2}bc^{n-2}-a^{n-2}bc^{m-2}\right) \\ =&2\left(a+b+c\right)f_{n-2,m-2}-2abc\cdot f_{n-3,m-3}-f_{n-2,m-1}-f_{n-1,m-2} \\ f_{n-2,m-1}+f_{n-1,m-2}=&\left(a+b+c\right)f_{n-2,m-2}-abc\cdot f_{n-3,m-3} \\ f_{n,m}=&\left(\sum_{cyc}ab\right)\cdot f_{n-1,m-1}-abc\left(a+b+c\right)\cdot f_{n-2,m-2}+a^2b^2c^2\cdot f_{n-3,m-3} \end{aligned} $$

下求 $f_{n,1}$

$$ \begin{aligned} f_{n,1}=&\sum_{cyc}\left(a^nb-ab^n\right)\\ =&\sum_{cyc}a\sum_{cyc}\left(a^{n-1}b-ab^{n-1}\right)-\sum_{cyc}\left(-a^2b^{n-1}+ab^{n-1}c-abc^{n-1}+a^2c^{n-1}\right)\\ =&\left(a+b+c\right)f_{n-1,1}-\sum_{cyc}\left(a^{n-1}c^{2}-a^{2}c^{n-1}\right)\\ =&\left(a+b+c\right)f_{n-1,1}-f_{n-1,2}\\ =&\left(a+b+c\right)f_{n-1,1}-\left(ab+bc+ca\right)f_{n-2,1}-a^2b^2c^2\cdot f_{n-4,-1} \\ =&\left(a+b+c\right)f_{n-1,1}-\left(ab+bc+ca\right)f_{n-2,1}+abc\cdot f_{n-3,1} \end{aligned} $$

下面是正宗做法，假设 $g_n\left(x\right)=x^n\bmod \left(x^3-sx^2+tx-u\right)$

那么将 $a^n$ 用 $g_{n}\left(a\right)$ 表示，最后答案就是用 $g_n,g_m$ 的系数和 $f_{1,1},f_{1,2},f_{2,2}$ 表示就行了

$g_n,g_m$ 的系数也是三次线性递推

文章目录