锐客网

  1. 首页 > it技术 > >

类欧几里得算法学习笔记

OI数论

这个东西看起来好恐怖啊QAQ.jpg搞了几天，QWQ
其实类欧几里得算法，就是和欧几里得算法类似（欧几里得算法就是gcd那一堆啦），但是其实只有时间复杂度的证明是和gcd一样的，其它的都完全不同,emmmm。
先前置两道例题：【luoug-T36097 整点与质数】【[COCI2009-2010#1] ALADIN
】【讲解by hdxrie】
【类欧几里得算法学习笔记】其实这个就是一个十分简单的类欧算法的应用
以前做到的时候还不知道，现在学了才知道，QAQ
我们可以从一个简单的式子来入门，并对其套路有一定的了解。
T ≤ 1 0 5 T\leq 10^5 T≤105组询问，每组对于给定的 n ≤ 1 0 9 n\leq 10^9 n≤109求下面式子在 m o d998244353 \rm mod\ 998244353 mod 998244353意义下的值 ( a , b ≥ 0 , c > 0 ) (a,b\geq 0,c> 0) (a,b≥0,c>0)：
∑ i = 0 n ? a i + b c ? \sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor i=0∑n??cai+b??

其实前面的 ? i p q ? \left\lfloor\frac{ip}{q}\right\rfloor ?qip??就是这个式子的简化版， b = 0 b=0 b=0。
显然这个不能直接 O ( n ) O(n) O(n)算，或者除法分块，所以我们要另寻它路。
首先我们可以分成两步考虑：
  1. a ≥ c a\geq c a≥c或者 b ≥ c b\geq c b≥c时
此时，我们显然可以将原式写成：
∑ i = 0 n ( ? a c ? i + ? b c ? + ? ( a % c ) i + ( b % c ) c ? ) \sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor\right) i=0∑n?(?ca??i+?cb??+?c(a%c)i+(b%c)??)
将其拆开可以得到：
? a c ? ∑ i = 0 n i + ∑ i = 0 n ? b c ? + ∑ i = 0 n ? ( a % c ) i + ( b % c ) c ? \left\lfloor\frac{a}{c}\right\rfloor\sum_{i=0}^ni+\sum_{i=0}^n\left\lfloor\frac{b}{c}\right\rfloor+\sum_{i=0}^n\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor ?ca??i=0∑n?i+i=0∑n??cb??+i=0∑n??c(a%c)i+(b%c)??
前面两个可以用公式 O ( 1 ) O(1) O(1)的求，而后面那个又是一个类似的子问题，递归求解即可。
所以我们令 f ( a , b , c , n ) = ∑ i = 0 n ? a i + b c ? f(a,b,c,n)=\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor f(a,b,c,n)=∑i=0n??cai+b??，那么原式可以写成：
f ( a , b , c , n ) = ? a c ? n × ( n + 1 ) 2 + ( n + 1 ) ? b c ? + f ( a % c , b % c , c , n ) f(a,b,c,n)=\left\lfloor\frac{a}{c}\right\rfloor\frac{n\times (n+1)}{2}+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\%c,b\%c,c,n) f(a,b,c,n)=?ca??2n×(n+1)?+(n+1)?cb??+f(a%c,b%c,c,n)
此时我们就把问题从 a ≥ c , b ≥ c a\geq c,b\geq c a≥c,b≥c转换 a , b < c a,b< c a,b
  1. 那么显然另外一种情况就是 a < c a< c a
其实，如果看了 h d x r i e \rm hdxrie hdxrie的关于 [ C O C I 2010 ] A L A D I N \rm [COCI2010]ALADIN [COCI2010]ALADIN的那个题的讲解，这个也就是相当于求一条直线下整点个数，具体讲解可以看这篇论文【洪华敦-类欧几里得算法】。
那么我们可以枚举整点的坐标，原式就可以转化成（这里 m = ? a n + b c ? ? 1 m=\lfloor\frac{an+b}{c}\rfloor-1 m=?can+b???1）：
f ( a , b , c , n ) = ∑ i = 0 n ∑ j = 1 m + 1 [ j ? ? a i + b c ? ] f(a,b,c,n)=\sum_{i=0}^n\sum_{j=1}^{m+1}[j\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor] f(a,b,c,n)=i=0∑n?j=1∑m+1?[j??cai+b??]
这里 [ a = 1 ] [a=1] [a=1]这种是逻辑判断符，如果里面语句为真，那么值为1，否则为0。
其实这里就是相当于一条 y = a x + b c y=\frac{ax+b}{c} y=cax+b?的直线，所以我们枚举 i i i就是枚举的 x x x， j j j就是 y y y，如果 j j j小于等于的话 ( i , j ) (i,j) (i,j)就是在这个直线下的整点。
然后我们先交换枚举顺序可以得到：
由于 a ? ? b ? a\leqslant \lfloor b\rfloor a??b?时也满足 a ? b a\leqslant b a?b，所以变换时可以把向下取整符号去掉。
f ( a , b , c , n ) = ∑ j = 1 m + 1 ∑ i = 0 n [ j ? ? a i + b c ? ] = ∑ j = 0 m ∑ i = 0 n [ j + 1 ? ? a i + b c ? ] = ∑ j = 0 m ∑ i = 0 n [ j + 1 ? a i + b c ] = ∑ j = 0 m ∑ i = 0 n [ j c + c ? a i + b ] = ∑ j = 0 m ∑ i = 0 n [ a i ? j c + c ? b ] = ∑ j = 0 m ∑ i = 0 n [ a i > j c + c ? b ? 1 ] = ∑ j = 0 m ∑ i = 0 n [ i > ? j c + c ? b ? 1 a ? ] \begin{aligned} f(a,b,c,n)=& \sum_{j=1}^{m+1}\sum_{i=0}^n[j\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[j+1\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[j+1\leqslant \frac{ai+b}{c}] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[jc+c\leqslant ai+b] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[ai\geqslant jc+c-b] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[ai> jc+c-b-1] \\ =& \sum_{j=0}^{m}\sum_{i=0}^n[i> \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor] \end{aligned} f(a,b,c,n)=======?j=1∑m+1?i=0∑n?[j??cai+b??]j=0∑m?i=0∑n?[j+1??cai+b??]j=0∑m?i=0∑n?[j+1?cai+b?]j=0∑m?i=0∑n?[jc+c?ai+b]j=0∑m?i=0∑n?[ai?jc+c?b]j=0∑m?i=0∑n?[ai>jc+c?b?1]j=0∑m?i=0∑n?[i>?ajc+c?b?1??]?
由于在 i ∈ [ 0 , n ] i\in[0,n] i∈[0,n]中的 i > ? j c + c ? b ? 1 a ? i> \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor i>?ajc+c?b?1??的只有 ? j c + c ? b ? 1 a ? ～ n \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\sim n ?ajc+c?b?1??～n，所以进而化简得：
f ( a , b , c , n ) = ∑ j = 0 m ( n ? ? j c + c ? b ? 1 a ? ) = ∑ j = 0 m n ? ∑ j = 0 m ? j c + c ? b ? 1 a ? =n × ( m + 1 ) ? f ( c , c ? b ? 1 , a , m ) \begin{aligned} f(a,b,c,n)=& \sum_{j=0}^{m}\left(n-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \\ =& \sum_{j=0}^{m}n-\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor \\ =& \ n\times (m+1)-f(c,c-b-1,a,m) \end{aligned} f(a,b,c,n)===?j=0∑m?(n??ajc+c?b?1??)j=0∑m?n?j=0∑m??ajc+c?b?1?? n×(m+1)?f(c,c?b?1,a,m)?
那么这样又可以将 f ( a , b , c , n ) ? f ( c , c ? b ? 1 , a , ? a n + b c ? ? 1 ) f(a,b,c,n)\Rightarrow f(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1) f(a,b,c,n)?f(c,c?b?1,a,?can+b???1)，又将问题变小了。
那么边界就是当：
  • n = 0 n=0 n=0时，直接返回 ? b c ? \lfloor\frac{b}{c}\rfloor ?cb??
  • a = 0 a=0 a=0时，就是 ( n + 1 ) × ? b c ? (n+1)\times \lfloor\frac{b}{c}\rfloor (n+1)×?cb??
f总结 f ( a , b , c , n ) = { ? b c ? n = 0 ( n + 1 ) × ? b c ? a = 0 ? a c ? n × ( n + 1 ) 2 + ( n + 1 ) ? b c ? + f ( a % c , b % c , c , n ) a ? co rb ? c n × ? a n + b c ? ? f ( c , c ? b ? 1 , a , m ) a < ca n db < c f(a,b,c,n)=\begin{cases}\lfloor\frac{b}{c}\rfloor& n=0\\ (n+1)\times \lfloor\frac{b}{c}\rfloor& a=0\\ \left\lfloor\frac{a}{c}\right\rfloor\frac{n\times (n+1)}{2}+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\%c,b\%c,c,n)& a\geqslant c\ or\ b\geqslant c\\ n\times \left\lfloor\frac{an+b}{c}\right\rfloor-f(c,c-b-1,a,m)& a< c\ and\ b< c\end{cases} f(a,b,c,n)=???????????cb??(n+1)×?cb???ca??2n×(n+1)?+(n+1)?cb??+f(a%c,b%c,c,n)n×?can+b???f(c,c?b?1,a,m)?n=0a=0a?c or b?ca 这时就已经可以写出一份十分简单的递归的代码了：
int S1(int n){return n*(n+1)/2; } int f(int a,int b,int c,int n){ if(!n) return b/c; if(!a) return (n+1)*(b/c); if(a>=c||b>=c)return S1(n)*(a/c)+n*(b/c)+f(a%c,b%c,c,n); return n*((a*n+b)/c)-f(c,c-b-1,a,(a*n+b)/c-1); }

关于复杂度，首先我们看 a ≥ c , b ≥ c a\geq c,b\geq c a≥c,b≥c的时候只需 O ( 1 ) O(1) O(1)就转移到了 a < c , b < c a< c,b< c a 有了初步的了解，我们就可以看看稍微难一点的：
同样的条件，再求下面两个式子的值：
∑ i = 0 n ( ? a i + b c ? ) 2 \sum_{i=0}^n\left(\left\lfloor\frac{ai+b}{c}\right\rfloor\right)^2 i=0∑n?(?cai+b??)2
和
∑ i = 0 n i ? a i + b c ? \sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor i=0∑n?i?cai+b??
之所以放在一起说，是因为这两个在求取的过程中会有联系，而且还要用到前面的 f f f。
首先我们令 h ( a , b , c , n ) = ∑ i = 0 n ( ? a i + b c ? ) 2 , g ( a , b , c , n ) = ∑ i = 0 n i ? a i + b c ? h(a,b,c,n)=\sum_{i=0}^n\left(\left\lfloor\frac{ai+b}{c}\right\rfloor\right)^2,g(a,b,c,n)=\sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor h(a,b,c,n)=∑i=0n?(?cai+b??)2,g(a,b,c,n)=∑i=0n?i?cai+b??
那么我们先来看 h h h的求法，和 f f f类似（其实类欧的套路都差不多是这样），我们分两块考虑：
  1. 当 a ≥ c a\geq c a≥c或者 b ≥ c b\geq c b≥c时：
显然同理有：
h ( a , b , c , n ) = ∑ i = 0 n ( ? a c ? i + ? b c ? + ? ( a % c ) i + ( b % c ) c ? ) 2 h(a,b,c,n)=\sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor\right)^2 h(a,b,c,n)=i=0∑n?(?ca??i+?cb??+?c(a%c)i+(b%c)??)2
我们把那个恐怖的括号打开，可以得到（ ( a + b + c ) 2 = a 2 + b 2 + c 2 + 2 a b + 2 b c + 2 a c (a+b+c)^2=a^2+b^2+c^2+2ab+2bc+2ac (a+b+c)2=a2+b2+c2+2ab+2bc+2ac）：
h ( a , b , c , n ) = ∑ i = 0 n ( ? a c ? i ) 2 + ∑ i = 0 n ( ? b c ? ) 2 + ∑ i = 0 n ( ? ( a % c ) i + ( b % c ) c ? ) 2 + ∑ i = 0 n 2 ? ? a c ? i ? ? b c ? + ∑ i = 0 n 2 ? ? b c ? ? ? ( a % c ) i + ( b % c ) c ? + ∑ i = 0 n 2 ? ? a c ? i ? ? ( a % c ) i + ( b % c ) c ? h(a,b,c,n)=\sum_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i\right)^2+\sum_{i=0}^{n}\left(\left\lfloor\frac{b}{c}\right\rfloor\right)^2+\sum_{i=0}^n\left(\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor\right)^2 \\ +\sum_{i=0}^n2\cdot \left\lfloor\frac{a}{c}\right\rfloor i\cdot \left\lfloor\frac{b}{c}\right\rfloor+\sum_{i=0}^n2\cdot\left\lfloor\frac{b}{c}\right\rfloor\cdot\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor+\sum_{i=0}^n2\cdot\left\lfloor\frac{a}{c}\right\rfloor i\cdot\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor h(a,b,c,n)=i=0∑n?(?ca??i)2+i=0∑n?(?cb??)2+i=0∑n?(?c(a%c)i+(b%c)??)2+i=0∑n?2??ca??i??cb??+i=0∑n?2??cb????c(a%c)i+(b%c)??+i=0∑n?2??ca??i??c(a%c)i+(b%c)??
我们把这一大坨，整理化简一下，可以得到：
由于 ∑ i = 0 n i 2 = n × ( n + 1 ) × ( 2 n + 1 ) 6 \sum_{i=0}^ni^2=\frac{n\times (n+1)\times(2n+1)}{6} ∑i=0n?i2=6n×(n+1)×(2n+1)?， ∑ i = 0 n i = n × ( n + 1 ) 2 \sum_{i=0}^ni=\frac{n\times(n+1)}{2} ∑i=0n?i=2n×(n+1)?
h ( a , b , c , n ) = ( ? a c ? ) 2 n × ( n + 1 ) × ( 2 n + 1 ) 6 + ( n + 1 ) × ( ? b c ? ) 2 + h ( a % c , b % c , c , n ) + 2 ? ? a c ? ? ? b c ? ? n × ( n + 1 ) 2 + 2 ? ? b c ? ? f ( a % c , b % c , c , n ) + 2 ? ? a c ? ? g ( a % c , b % c , c , n ) h(a,b,c,n)=\left(\left\lfloor\frac{a}{c}\right\rfloor\right)^2\frac{n\times(n+1)\times(2n+1)}{6}+(n+1)\times\left(\left\lfloor\frac{b}{c}\right\rfloor\right)^2+h(a\%c,b\%c,c,n) \\ +2\cdot \left\lfloor\frac{a}{c}\right\rfloor\cdot \left\lfloor\frac{b}{c}\right\rfloor\cdot\frac{n\times(n+1)}{2}+2\cdot\left\lfloor\frac{b}{c}\right\rfloor\cdot f(a\%c,b\%c,c,n)+2\cdot\left\lfloor\frac{a}{c}\right\rfloor\cdot g(a\%c,b\%c,c,n) h(a,b,c,n)=(?ca??)26n×(n+1)×(2n+1)?+(n+1)×(?cb??)2+h(a%c,b%c,c,n)+2??ca????cb???2n×(n+1)?+2??cb???f(a%c,b%c,c,n)+2??ca???g(a%c,b%c,c,n)
递归处理就可以了（假设我们现在知道 g g g如何计算）。
  1. 我们继续考虑当 a < c , b < c a< c,b< c a
通过 f f f的经验，我们照着之前的变换一下看（ m m m的意义同前面）：
h ( a , b , c , n ) = ∑ i = 0 n ( ∑ j = 1 m + 1 [ j ? ? a i + b c ? ] ) 2 h(a,b,c,n)=\sum_{i=0}^n\left(\sum_{j=1}^{m+1}[j\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor]\right)^2 h(a,b,c,n)=i=0∑n?(j=1∑m+1?[j??cai+b??])2
我们将后面拆成两个式子，然后按照 f f f的方式变换：
h ( a , b , c , n ) = ∑ i = 0 n ( ∑ j = 1 m + 1 [ j ? ? a i + b c ? ] ) × ( ∑ k = 1 m + 1 [ k ? ? a i + b c ? ] ) = ∑ i = 0 n ( ∑ j = 0 m [ j + 1 ? a i + b c ] ) × ( ∑ k = 0 m [ k + 1 ? a i + b c ] ) = ∑ i = 0 n ( ∑ j = 0 m [ j c + c ? a i + b ] ) × ( ∑ k = 0 m [ k c + c ? a i + b ] ) = ∑ i = 0 n ( ∑ j = 0 m [ a i ? j c + c ? b ] ) × ( ∑ k = 0 m [ a i ? k c + c ? b ] ) = ∑ i = 0 n ( ∑ j = 0 m [ a i > j c + c ? b ? 1 ] ) × ( ∑ k = 0 m [ a i > k c + c ? b ? 1 ] ) \begin{aligned} h(a,b,c,n)=& \sum_{i=0}^n\left(\sum_{j=1}^{m+1}[j\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor]\right)\times \left(\sum_{k=1}^{m+1}[k\leqslant \left\lfloor\frac{ai+b}{c}\right\rfloor]\right) \\ =& \sum_{i=0}^n\left(\sum_{j=0}^{m}[j+1\leqslant \frac{ai+b}{c}]\right)\times \left(\sum_{k=0}^{m}[k+1\leqslant \frac{ai+b}{c}]\right) \\ =& \sum_{i=0}^n\left(\sum_{j=0}^{m}[jc+c\leqslant {ai+b}]\right)\times \left(\sum_{k=0}^{m}[kc+c\leqslant {ai+b}]\right) \\ =& \sum_{i=0}^n\left(\sum_{j=0}^{m}[ai\geqslant jc+c-b]\right)\times \left(\sum_{k=0}^{m}[ai\geqslant {kc+c-b}]\right) \\ =& \sum_{i=0}^n\left(\sum_{j=0}^{m}[ai> jc+c-b-1]\right)\times \left(\sum_{k=0}^{m}[ai> {kc+c-b-1}]\right) \end{aligned} h(a,b,c,n)=====?i=0∑n?(j=1∑m+1?[j??cai+b??])×(k=1∑m+1?[k??cai+b??])i=0∑n?(j=0∑m?[j+1?cai+b?])×(k=0∑m?[k+1?cai+b?])i=0∑n?(j=0∑m?[jc+c?ai+b])×(k=0∑m?[kc+c?ai+b])i=0∑n?(j=0∑m?[ai?jc+c?b])×(k=0∑m?[ai?kc+c?b])i=0∑n?(j=0∑m?[ai>jc+c?b?1])×(k=0∑m?[ai>kc+c?b?1])?
然后我们同理，交换枚举顺序，可以得到：
h ( a , b , c , n ) = ∑ j = 0 m ∑ k = 0 m ∑ i = 0 n [ a i > max ? ( j c ? b ? 1 , k c ? b ? 1 ) ] = ∑ j = 0 m ∑ k = 0 m ∑ i = 0 n [ i > max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) ] \begin{aligned} h(a,b,c,n)=& \sum_{j=0}^m\sum_{k=0}^m\sum_{i=0}^n[ai> \max(jc-b-1,kc-b-1)] \\ =& \sum_{j=0}^m\sum_{k=0}^m\sum_{i=0}^n[i> \max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor)] \end{aligned} h(a,b,c,n)==?j=0∑m?k=0∑m?i=0∑n?[ai>max(jc?b?1,kc?b?1)]j=0∑m?k=0∑m?i=0∑n?[i>max(?ajc+c?b?1??,?akc+c?b?1??)]?
同样， i ∈ [ 0 , n ] i\in[0,n] i∈[0,n]的 i > max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) i> \max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor) i>max(?ajc+c?b?1??,?akc+c?b?1??)的只有 > max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) ～ n > \max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor)\sim n >max(?ajc+c?b?1??,?akc+c?b?1??)～n这一部分，所以原式还可以写成：
h ( a , b , c , n ) = ∑ j = 0 m ∑ k = 0 m ( n ? max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) ) = n ( m + 1 ) 2 ? ∑ j = 0 m ∑ k = 0 m max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) \begin{aligned} h(a,b,c,n)=& \sum_{j=0}^{m}\sum_{k=0}^{m}\left(n-\max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor)\right) \\ =& n(m+1)^2-\sum_{j=0}^{m}\sum_{k=0}^{m}\max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor) \end{aligned} h(a,b,c,n)==?j=0∑m?k=0∑m?(n?max(?ajc+c?b?1??,?akc+c?b?1??))n(m+1)2?j=0∑m?k=0∑m?max(?ajc+c?b?1??,?akc+c?b?1??)?
这里的 max ? \max max不好处理，但是我们可以通过枚举当前这个是 max ? \max max的贡献，首先 j ? k j\geqslant k j?k的部分为：
∑ j = 0 m ( j + 1 ) ? j c + c ? b ? 1 a ? \sum_{j=0}^{m}(j+1)\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor j=0∑m?(j+1)?ajc+c?b?1??
因为对于每个 j j j，都有 0 ～ j 0\sim j 0～j也就是 j + 1 j+1 j+1个 k k k比它小，所以每个的贡献次数是 j + 1 j+1 j+1次。
那么同理对于 j ? k j\leqslant k j?k的部分就是：
∑ k = 0 m ( k + 1 ) ? k c + c ? b ? 1 a ? \sum_{k=0}^{m}(k+1)\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor k=0∑m?(k+1)?akc+c?b?1??
但是这两个加起来，会把 j = k j=k j=k的部分多加一次，所以我们减去多加了的这个部分：
∑ j = 0 m ? j c + c ? b ? 1 a ? \sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor j=0∑m??ajc+c?b?1??
那么原式就可以变成：
h ( a , b , c , n ) = n ( m + 1 ) 2 ? ∑ j = 0 m ∑ k = 0 m max ? ( ? j c + c ? b ? 1 a ? , ? k c + c ? b ? 1 a ? ) = n ( m + 1 ) 2 ? ( ∑ j = 0 m ( j + 1 ) ? j c + c ? b ? 1 a ? + ∑ k = 0 m ( k + 1 ) ? k c + c ? b ? 1 a ? ? ∑ j = 0 m ? j c + c ? b ? 1 a ? ) = n ( m + 1 ) 2 ? ( 2 ? ∑ j = 0 m ( j + 1 ) ? j c + c ? b ? 1 a ? ? ∑ j = 0 m ? j c + c ? b ? 1 a ? ) \begin{aligned} h(a,b,c,n)=& n(m+1)^2-\sum_{j=0}^{m}\sum_{k=0}^{m}\max(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor,\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor) \\ =& n(m+1)^2-\left(\sum_{j=0}^{m}(j+1)\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+\sum_{k=0}^{m}(k+1)\left\lfloor\frac{kc+c-b-1}{a}\right\rfloor-\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \\ =& n(m+1)^2-\left(2\cdot \sum_{j=0}^{m}(j+1)\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor-\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \end{aligned} h(a,b,c,n)===?n(m+1)2?j=0∑m?k=0∑m?max(?ajc+c?b?1??,?akc+c?b?1??)n(m+1)2?(j=0∑m?(j+1)?ajc+c?b?1??+k=0∑m?(k+1)?akc+c?b?1???j=0∑m??ajc+c?b?1??)n(m+1)2?(2?j=0∑m?(j+1)?ajc+c?b?1???j=0∑m??ajc+c?b?1??)?
我们把 ( j + 1 ) (j+1) (j+1)打开，然后整理可以得到：
h ( a , b , c , n ) = n ( m + 1 ) 2 ? ( 2 ? ∑ j = 0 m j ? j c + c ? b ? 1 a ? + 2 ? ∑ j = 0 m ? j c + c ? b ? 1 a ? ? ∑ j = 0 m ? j c + c ? b ? 1 a ? ) = n ( m + 1 ) 2 ? ( 2 ? ∑ j = 0 m j ? j c + c ? b ? 1 a ? + ∑ j = 0 m ? j c + c ? b ? 1 a ? ) = n ( m + 1 ) 2 ? 2 ? g ( c , c ? b ? 1 , a , m ) ? f ( c , c ? b ? 1 , a , m ) \begin{aligned} h(a,b,c,n)=& n(m+1)^2-\left(2\cdot \sum_{j=0}^{m}j\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+2\cdot\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor-\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \\ =& n(m+1)^2-\left(2\cdot \sum_{j=0}^{m}j\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+\sum_{j=0}^{m}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \\ =& n(m+1)^2-2\cdot g(c,c-b-1,a,m)-f(c,c-b-1,a,m) \end{aligned} h(a,b,c,n)===?n(m+1)2?(2?j=0∑m?j?ajc+c?b?1??+2?j=0∑m??ajc+c?b?1???j=0∑m??ajc+c?b?1??)n(m+1)2?(2?j=0∑m?j?ajc+c?b?1??+j=0∑m??ajc+c?b?1??)n(m+1)2?2?g(c,c?b?1,a,m)?f(c,c?b?1,a,m)?
那么我们同样可以将其转移到更小的问题上，递归计算即可。
边界同理：
  • 当 n = 0 n=0 n=0时，就是 ( b c ) 2 \left(\frac{b}{c}\right)^2 (cb?)2
  • 当 a = 0 a=0 a=0时，就是 ( n + 1 ) × ( b c ) 2 (n+1)\times \left(\frac{b}{c}\right)^2 (n+1)×(cb?)2
h总结 h ( a , b , c , n ) = { ( b c ) 2 n = 0 ( n + 1 ) × ( b c ) 2 a = 0 ( ? a c ? ) 2 n ( n + 1 ) ( 2 n + 1 ) 6 + ( n + 1 ) ( ? b c ? ) 2 + h ( a % c , b % c , c , n ) + 2 ? a c ? ? b c ? n ( n + 1 ) 2 + 2 ? b c ? f ( a % c , b % c , c , n ) + 2 ? a c ? g ( a % c , b % c , c , n ) a ? co rb ? c n ( m + 1 ) 2 ? 2 ? g ( c , c ? b ? 1 , a , m ) ? f ( c , c ? b ? 1 , a , m ) a < ca n db < c h(a,b,c,n)=\begin{cases}\left(\frac{b}{c}\right)^2& n=0\\ (n+1)\times \left(\frac{b}{c}\right)^2& a=0\\ \left(\left\lfloor\frac{a}{c}\right\rfloor\right)^2\frac{n(n+1)(2n+1)}{6}+(n+1)\left(\left\lfloor\frac{b}{c}\right\rfloor\right)^2+h(a\%c,b\%c,c,n) +2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor\frac{n(n+1)}{2}+2\left\lfloor\frac{b}{c}\right\rfloor f(a\%c,b\%c,c,n)+2\left\lfloor\frac{a}{c}\right\rfloor g(a\%c,b\%c,c,n)& a\geqslant c\ or\ b\geqslant c\\ n(m+1)^2-2\cdot g(c,c-b-1,a,m)-f(c,c-b-1,a,m)& a< c\ and\ b< c\end{cases} h(a,b,c,n)=????????????(cb?)2(n+1)×(cb?)2(?ca??)26n(n+1)(2n+1)?+(n+1)(?cb??)2+h(a%c,b%c,c,n)+2?ca???cb??2n(n+1)?+2?cb??f(a%c,b%c,c,n)+2?ca??g(a%c,b%c,c,n)n(m+1)2?2?g(c,c?b?1,a,m)?f(c,c?b?1,a,m)?n=0a=0a?c or b?ca 代码同样十分好写，仿照上面的即可，这里就不写了。
接下来只剩下对于 g g g的求法了。
g g g相对 h h h来说就很好变换了，直接跟着套路走：
  1. 当 a ? c , b ? c a\geqslant c,b\geqslant c a?c,b?c时：
g ( a , b , c , n ) = ∑ i = 0 n i ? a i + b c ? = ∑ i = 0 n ? a c ? i 2 + ? b c ? i + i ? ( a % c ) i + ( b % c ) c ? = ? a c ? n ( n + 1 ) ( 2 n + 1 ) 6 + ? b c ? n ( n + 1 ) 2 + g ( a % c , b % c , c , n ) \begin{aligned} g(a,b,c,n)=& \sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor \\ =& \sum_{i=0}^n\left\lfloor\frac{a}{c}\right\rfloor i^2+\left\lfloor\frac{b}{c}\right\rfloor i+i\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor \\ =& \left\lfloor\frac{a}{c}\right\rfloor\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor\frac{n(n+1)}{2}+g(a\%c,b\%c,c,n) \end{aligned} g(a,b,c,n)===?i=0∑n?i?cai+b??i=0∑n??ca??i2+?cb??i+i?c(a%c)i+(b%c)???ca??6n(n+1)(2n+1)?+?cb??2n(n+1)?+g(a%c,b%c,c,n)?
  1. 当 a < c , b < c a< c,b< c a
根据套路，我们转换成这个形式：
g ( a , b , c , n ) = ∑ j = 0 m ∑ i = 0 n i [ i > ? j c + c ? b ? 1 a ? ] = ∑ j = 0 m ∑ i = ? j c + c ? b ? 1 a ? + 1 n i = ∑ j = 0 m ( ∑ i = 0 n i ? ∑ i = 0 ? j c + c ? b ? 1 a ? i ) = ∑ j = 0 m n ( n + 1 ) 2 ? ? j c + c ? b ? 1 a ? ? ( ? j c + c ? b ? 1 a ? + 1 ) 2 = 1 2 ( n ( n + 1 ) ( m + 1 ) ? ∑ j = 0 m ( ? j c + c ? b ? 1 a ? ) 2 ? ? j c + c ? b ? 1 a ? ) = 1 2 ( n ( n + 1 ) ( m + 1 ) ? h ( c , c ? b ? 1 , a , m ) ? f ( c , c ? b ? 1 , a , m ) ) \begin{aligned} g(a,b,c,n)=& \sum_{j=0}^{m}\sum_{i=0}^ni[i> \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor] \\ =& \sum_{j=0}^{m}\sum_{i=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1}^ni \\ =& \sum_{j=0}^{m}\left(\sum_{i=0}^ni-\sum_{i=0}^{\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor}i\right) \\ =& \sum_{j=0}^{m}\frac{n(n+1)}{2}-\frac{\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\cdot\left(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor+1\right)}{2} \\ =& \frac{1}{2}\left(n(n+1)(m+1)-\sum_{j=0}^{m}\left(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)^2-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right) \\ =& \frac{1}{2}\left(n(n+1)(m+1)-h(c,c-b-1,a,m)-f(c,c-b-1,a,m)\right) \end{aligned} g(a,b,c,n)======?j=0∑m?i=0∑n?i[i>?ajc+c?b?1??]j=0∑m?i=?ajc+c?b?1??+1∑n?ij=0∑m?????i=0∑n?i?i=0∑?ajc+c?b?1???i????j=0∑m?2n(n+1)??2?ajc+c?b?1???(?ajc+c?b?1??+1)?21?(n(n+1)(m+1)?j=0∑m?(?ajc+c?b?1??)2??ajc+c?b?1??)21?(n(n+1)(m+1)?h(c,c?b?1,a,m)?f(c,c?b?1,a,m))?
由此我们可以直接判断后递归计算即可。
边界条件还是一样的：
  • 当 n = 0 n=0 n=0时，为 0 0 0。
  • 当 a = 0 a=0 a=0时，为 ? b c ? ( n ( n + 1 ) 2 ) \lfloor\frac{b}{c}\rfloor(\frac{n(n+1)}{2}) ?cb??(2n(n+1)?)
g总结 g ( a , b , c , n ) = { 0 n = 0 ? b c ? ( n ( n + 1 ) 2 ) a = 0 ? a c ? n ( n + 1 ) ( 2 n + 1 ) 6 + ? b c ? n ( n + 1 ) 2 + g ( a % c , b % c , c , n ) a ? co rb ? c 1 2 ( n ( n + 1 ) ( m + 1 ) ? h ( c , c ? b ? 1 , a , m ) ? f ( c , c ? b ? 1 , a , m ) ) a < ca n db < c g(a,b,c,n)=\begin{cases}0& n=0\\ \lfloor\frac{b}{c}\rfloor(\frac{n(n+1)}{2})& a=0\\ \left\lfloor\frac{a}{c}\right\rfloor\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor\frac{n(n+1)}{2}+g(a\%c,b\%c,c,n)& a\geqslant c\ or\ b\geqslant c\\ \frac{1}{2}\left(n(n+1)(m+1)-h(c,c-b-1,a,m)-f(c,c-b-1,a,m)\right)& a< c\ and\ b< c\end{cases} g(a,b,c,n)=??????????0?cb??(2n(n+1)?)?ca??6n(n+1)(2n+1)?+?cb??2n(n+1)?+g(a%c,b%c,c,n)21?(n(n+1)(m+1)?h(c,c?b?1,a,m)?f(c,c?b?1,a,m))?n=0a=0a?c or b?ca 代码同理。
技巧：为了方便求取 g , h g,h g,h，通常我们可以在一个递归里面写，可以降低复杂度，并且写起了也挺简单的。
  • 【模板-IN-luogu】
这个算是个简单的模板了，求的就是上面讲的 f , h , g f,h,g f,h,g函数：
//代码中的h,g的意义对换了一下，懒得改了 #include #include #include #define ll long long using namespace std; const ll Mod=998244353; const ll inv2=499122177,inv6=166374059; ll S1(ll x){if(x>=Mod)x%=Mod; return (x*(x+1)%Mod)*inv2%Mod; } ll S2(ll x){if(x>=Mod)x%=Mod; return (x*(x+1)%Mod*(x+x+1)%Mod)*inv6%Mod; } ll Sqr(ll x){return x*x%Mod; } struct node{ ll f,g,h; void clear(){f=g=h=0; } node(){} node(ll a,ll b,ll c):f(a),g(b),h(c){} void out(){printf("%lld %lld %lld\n",f,g,h); } }; node calc(ll a,ll b,ll c,ll n){ node ans,res; ans.clear(); ll m,t1,t2,s1,s2; if(!n){ans.f=b/c; ans.g=Sqr(b/c); return ans; } if(!a){ t1=b/c; ans.f=(n+1ll)*t1%Mod; ans.g=(n+1ll)*Sqr(t1)%Mod; ans.h=S1(n)*t1%Mod; return ans; } if(a>=c||b>=c){ t1=a/c; t2=b/c; res=calc(a%c,b%c,c,n); s1=S1(n); s2=S2(n); ans.f=(((s1*t1%Mod)+(n+1ll)*t2%Mod)%Mod+res.f)%Mod; ans.g=(((Sqr(t1)*s2%Mod+(n+1ll)*Sqr(t2)%Mod)%Mod)+((t1*t2%Mod)*2ll*s1%Mod+(t1*2ll*res.h%Mod))%Mod+(res.g+t2*2ll*res.f%Mod)%Mod)%Mod; ans.h=((s2*t1%Mod+s1*t2%Mod)+res.h)%Mod; return ans; } m=(n*a+b)/c-1; res=calc(c,c-b-1,a,m); ll w1=n*(m+1)%Mod,w2=n*(n+1)%Mod,w3=m+1; if(w3>=Mod)w3%=Mod; ans.f=(w1-res.f)%Mod; if(ans.f<0)ans.f+=Mod; ans.g=((w1*w3)%Mod-((res.h*2ll%Mod+res.f)%Mod))%Mod; if(ans.g<0)ans.g+=Mod; ans.h=((w2*w3)%Mod-(res.f+res.g)%Mod)%Mod*inv2%Mod; if(ans.h<0)ans.h+=Mod; return ans; } int a,b,c,n,T; int main(){ for(scanf("%d",&T); T--; ){scanf("%d%d%d%d",&n,&a,&b,&c); calc(a,b,c,n).out(); } return 0; }

我们其实可以求取更加一般化的式子，如这道模板题【IN-loj】
题意就是多组询问，给定 k 1 , k 2 , a , b , c , n k_1,k_2,a,b,c,n k1?,k2?,a,b,c,n求下面式子在 m o d998244353 \rm mod\ 998244353 mod 998244353意义下的值。
∑ i = 0 n i k 1 ? a i + b c ? k 2 \sum_{i=0}^ni^{k_1}\left\lfloor\frac{ai+b}{c}\right\rfloor^{k_2} i=0∑n?ik1??cai+b??k2?
数据范围见原题面。
  • 当 k 1 = 0 , k 2 = 1 k_1=0,k_2=1 k1?=0,k2?=1时，就是 f f f函数。
  • 当 k 1 = 0 , k 2 = 2 k_1=0,k_2=2 k1?=0,k2?=2时，就是 h h h函数。
  • 当 k 1 = 1 , k 2 = 1 k_1=1,k_2=1 k1?=1,k2?=1时，就是 g g g函数。
那么当 k 1 , k 2 k_1,k_2 k1?,k2?不为上面的那些情况的时候应该怎么办呢？
我们还是按照套路来分析，我们令 F ( k 1 , k 2 , a , b , c , n ) = ∑ i = 0 n i k 1 ? a i + b c ? k 2 F(k_1,k_2,a,b,c,n)=\sum_{i=0}^ni^{k_1}\left\lfloor\frac{ai+b}{c}\right\rfloor^{k_2} F(k1?,k2?,a,b,c,n)=∑i=0n?ik1??cai+b??k2?：
  • 当 a ≥ c , b ≥ c a\geq c,b\geq c a≥c,b≥c时：
F ( k 1 , k 2 , a , b , c , n ) = ∑ i = 0 n i k 1 ( ? a c ? i + ? b c ? + ? ( a % c ) i + ( b % c ) c ? ) k 2 F(k_1,k_2,a,b,c,n)=\sum_{i=0}^ni^{k_1}\left(\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor\frac{(a\%c)i+(b\%c)}{c}\right\rfloor\right)^{k_2} F(k1?,k2?,a,b,c,n)=i=0∑n?ik1?(?ca??i+?cb??+?c(a%c)i+(b%c)??)k2?
用二项式定理，我们可以将后面的括号展开得到：
用二项式定理推导一下可以得到
( a + b + c ) n = ∑ i + j + k = n C n i C n ? i j a i b j c k (a+b+c)^n=\sum_{i+j+k=n}C_{n}^iC_{n-i}^ja^ib^jc^k (a+b+c)n=∑i+j+k=n?Cni?Cn?ij?aibjck
F ( k 1 , k 2 , a , b , c , n ) = ∑ I = 0 n ∑ i + j + k = k 2 C k 2 i C k 2 ? i j ? a c ? i ? b c ? j ( I k 1 + i ) ? ( a % c ) I + ( b % c ) c ? k = ∑ i + j + k = k 2 C k 2 i C k 2 ? i j ? a c ? i ? b c ? j ∑ I = 0 n ( I k 1 + i ) ? ( a % c ) I + ( b % c ) c ? k 0 ≤ i , j , k F(k_1,k_2,a,b,c,n)=\sum_{I=0}^n\sum_{i+j+k=k_2}C_{k_2}^iC_{k_2-i}^j\left\lfloor\frac{a}{c}\right\rfloor^i\left\lfloor\frac{b}{c}\right\rfloor^j\left(I^{k_1+i}\right)\left\lfloor\frac{(a\%c)I+(b\%c)}{c}\right\rfloor^{k} \\ =\sum_{i+j+k=k_2}C_{k_2}^iC_{k_2-i}^j\left\lfloor\frac{a}{c}\right\rfloor^i\left\lfloor\frac{b}{c}\right\rfloor^j\sum_{I=0}^n\left(I^{k_1+i}\right)\left\lfloor\frac{(a\%c)I+(b\%c)}{c}\right\rfloor^{k} \\ 0\leq i,j,k F(k1?,k2?,a,b,c,n)=I=0∑n?i+j+k=k2?∑?Ck2?i?Ck2??ij??ca??i?cb??j(Ik1?+i)?c(a%c)I+(b%c)??k=i+j+k=k2?∑?Ck2?i?Ck2??ij??ca??i?cb??jI=0∑n?(Ik1?+i)?c(a%c)I+(b%c)??k0≤i,j,k
我们可以发现，最后面那堆等于 F ( k 1 + i , k , a % c , b % c , c , n ) F(k_1+i,k,a\%c,b\%c,c,n) F(k1?+i,k,a%c,b%c,c,n)，所以递归处理即可。
  • 当 a < c , b < c a< c,b< c a
我们知道 x k = ∑ i = 0 x ? 1 ( i + 1 ) k ? i k x^k=\sum_{i=0}^{x-1}(i+1)^k-i^k xk=∑i=0x?1?(i+1)k?ik
因为其等于： x k ? ( x ? 1 ) k + ( x ? 1 ) k ? ( x ? 2 ) k + ? ? 0 k = x k ? 0 = x k x^k-(x-1)^k+(x-1)^k-(x-2)^k+\cdots-0^k=x^k-0=x^k xk?(x?1)k+(x?1)k?(x?2)k+??0k=xk?0=xk
那么我们用其来变换原式得到：
F ( k 1 , k 2 , a , b , c , n ) = ∑ i = 0 n i k 1 ∑ j = 0 ? a i + b c ? ? 1 ( j + 1 ) k 2 ? j k 2 F(k_1,k_2,a,b,c,n)=\sum_{i=0}^ni^{k_1}\sum_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1}(j+1)^{k_2}-j^{k_2} F(k1?,k2?,a,b,c,n)=i=0∑n?ik1?j=0∑?cai+b???1?(j+1)k2??jk2?
我们交换枚举顺序可以得到（ m = ? a n + b c ? ? 1 m=\left\lfloor\frac{an+b}{c}\right\rfloor-1 m=?can+b???1）：
F ( k 1 , k 2 , a , b , c , n ) = ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 n i k 1 [ j ≤ ? a i + b c ? ] = ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 n i k 1 [ i < ? j c + c ? b ? 1 a ? ] = ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ( ∑ i = 0 n i k 1 ? ∑ i = 0 ? j c + c ? b ? 1 a ? i k 1 ) \begin{aligned} F(k_1,k_2,a,b,c,n)=& \sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^ni^{k_1}[j\leq\left\lfloor\frac{ai+b}{c}\right\rfloor] \\ =& \sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^ni^{k_1}[i< \left\lfloor\frac{jc+c-b-1}{a}\right\rfloor] \\ =& \sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\left(\sum_{i=0}^{n}i^{k_1}-\sum_{i=0}^{\lfloor\frac{jc+c-b-1}{a}\rfloor}i^{k_1}\right) \end{aligned} F(k1?,k2?,a,b,c,n)===?j=0∑m?((j+1)k2??jk2?)i=0∑n?ik1?[j≤?cai+b??]j=0∑m?((j+1)k2??jk2?)i=0∑n?ik1?[i 我们接下来将前面那一堆（也就是相当于 ( m + 1 ) k 2 (m+1)^{k_2} (m+1)k2?）乘进后面，得到：
F ( k 1 , k 2 , a , b , c , n ) = ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 n i k 1 ? ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 ? j c + c ? b ? 1 a ? i k 1 = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 ? j c + c ? b ? 1 a ? i k 1 \begin{aligned} F(k_1,k_2,a,b,c,n)=& \sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^n i^{k_1}-\sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^{\lfloor\frac{jc+c-b-1}{a}\rfloor}i^{k_1} \\ =& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^{\lfloor\frac{jc+c-b-1}{a}\rfloor}i^{k_1} \end{aligned} F(k1?,k2?,a,b,c,n)==?j=0∑m?((j+1)k2??jk2?)i=0∑n?ik1??j=0∑m?((j+1)k2??jk2?)i=0∑?ajc+c?b?1???ik1?(m+1)k2?i=0∑n?ik1??j=0∑m?((j+1)k2??jk2?)i=0∑?ajc+c?b?1???ik1??
而我们知道，关于自然数幂的前缀和是一个关于幂次+1的多项式，所以我们可以用拉格朗日插值（或者高斯消元）把其系数求出来，然后就可以带入到后面那一堆，再用二项式定理展开，得到：
假设 ∑ i = 0 k + 1 a k , i x i = ∑ i = 0 x i k \sum_{i=0}^{k+1}a_{k,i}x^i=\sum_{i=0}^xi^k ∑i=0k+1?ak,i?xi=∑i=0x?ik
F ( k 1 , k 2 , a , b , c , n ) = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ j = 0 m ( ( j + 1 ) k 2 ? j k 2 ) ∑ i = 0 ? j c + c ? b ? 1 a ? i k 1 = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ k = 0 k 2 ? 1 ( ∑ j = 0 m C k 2 k j k ? ∑ i = 0 ? j c + c ? b ? 1 a ? i k 1 ) = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ k = 0 k 2 ? 1 ( ∑ j = 0 m C k 2 k j k ? ∑ i = 0 k 1 + 1 a k 1 , i ( ? j c + c ? b ? 1 a ? ) i ) = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ k = 0 k 2 ? 1 ∑ i = 0 k 1 + 1 C k 2 k a k 1 , i ? ∑ j = 0 m j k ( ? j c + c ? b ? 1 a ? ) i = ( m + 1 ) k 2 ∑ i = 0 n i k 1 ? ∑ k = 0 k 2 ? 1 ∑ i = 0 k 1 + 1 C k 2 k a k 1 , i ? F ( k , i , c , c ? b ? 1 , a , m ) \begin{aligned} F(k_1,k_2,a,b,c,n)=& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{j=0}^{m}\left((j+1)^{k_2}-j^{k_2}\right)\sum_{i=0}^{\lfloor\frac{jc+c-b-1}{a}\rfloor}i^{k_1} \\ =& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{k=0}^{k_2-1}\left(\sum_{j=0}^mC_{k_2}^kj^k\cdot \sum_{i=0}^{\lfloor\frac{jc+c-b-1}{a}\rfloor}i^{k_1}\right) \\ =& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{k=0}^{k_2-1}\left(\sum_{j=0}^mC_{k_2}^kj^k\cdot \sum_{i=0}^{k_1+1}a_{k_1,i}\left(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)^i\right) \\ =& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{k=0}^{k_2-1}\sum_{i=0}^{k_1+1}C_{k_2}^ka_{k_1,i}\cdot \sum_{j=0}^mj^k\left(\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\right)^i \\ =& (m+1)^{k_2}\sum_{i=0}^n i^{k_1}-\sum_{k=0}^{k_2-1}\sum_{i=0}^{k_1+1}C_{k_2}^ka_{k_1,i}\cdot F(k,i,c,c-b-1,a,m) \end{aligned} F(k1?,k2?,a,b,c,n)=====?(m+1)k2?i=0∑n?ik1??j=0∑m?((j+1)k2??jk2?)i=0∑?ajc+c?b?1???ik1?(m+1)k2?i=0∑n?ik1??k=0∑k2??1????j=0∑m?Ck2?k?jk?i=0∑?ajc+c?b?1???ik1????(m+1)k2?i=0∑n?ik1??k=0∑k2??1?(j=0∑m?Ck2?k?jk?i=0∑k1?+1?ak1?,i?(?ajc+c?b?1??)i)(m+1)k2?i=0∑n?ik1??k=0∑k2??1?i=0∑k1?+1?Ck2?k?ak1?,i??j=0∑m?jk(?ajc+c?b?1??)i(m+1)k2?i=0∑n?ik1??k=0∑k2??1?i=0∑k1?+1?Ck2?k?ak1?,i??F(k,i,c,c?b?1,a,m)?
其中，有一步是这样变换的：
∑ i = 0 x ? 1 ( i + 1 ) k ? i k = ∑ i = 0 x ? 1 ∑ j = 0 k C k j i j ? i k = ∑ i = 0 x ? 1 ∑ j = 0 k ? 1 C k j i j = ∑ j = 0 k ? 1 ( ∑ i = 0 x ? 1 C k j i j ) \sum_{i=0}^{x-1}(i+1)^k-i^k=\sum_{i=0}^{x-1}\sum_{j=0}^kC_{k}^ji^j-i^k \\=\sum_{i=0}^{x-1}\sum_{j=0}^{k-1}C_{k}^{j}i^j \\=\sum_{j=0}^{k-1}\left(\sum_{i=0}^{x-1}C_{k}^ji^j\right) i=0∑x?1?(i+1)k?ik=i=0∑x?1?j=0∑k?Ckj?ij?ik=i=0∑x?1?j=0∑k?1?Ckj?ij=j=0∑k?1?(i=0∑x?1?Ckj?ij)
那么，这个和前面的其实一样，递归计算就好啦，只不过要提前预处理一下系数和组合数。
k 1 , k 2 k_1,k_2 k1?,k2?比较小，所以每次算的时候暴力枚举一下（或者可以用 F F T FFT FFT之类的优化一下）就行了。
#include #include #include #define ll long long using namespace std; const int M=13; const ll Mod=1e9+7; ll y[M],C[M][M],F[M][M][44]; ll fpow(ll a,ll b=Mod-2){ a%=Mod; if(a<0)a+=Mod; ll res=1; for(; b; b>>=1,a=(a*a)%Mod)if(b&1)res=(res*a)%Mod; return res; } struct Ply{ ll x[M]; void clear(){memset(x,0,sizeof(x)); } Ply(){memset(x,0,sizeof(x)); } Ply operator +(const Ply &a)const{ Ply ans; for(int i=0; i=0; i--)ans=(ans*a%Mod+x[i])%Mod; return ans; } }A[M],B[M]; void calc(Ply &a,int n){ Ply xx,yy; for(int i=0; i<=n; i++){ xx.x[0]=y[i]; for(int j=0; j<=n; j++)if(i^j)xx.x[0]=xx.x[0]*fpow(i-j)%Mod; for(int j=0; j<=n; j++)if(j^i){yy.x[0]=Mod-j; yy.x[1]=1; xx=xx*yy; } a=a+xx; xx.clear(); } } ll f(int k1,int k2,ll a,ll b,ll c,ll n,int d=0){ if(~F[k1][k2][d]) return F[k1][k2][d]; ll ans=0; if(!a) ans=B[k1](n,k1)*fpow(b/c,k2)%Mod; else if(!k2) ans=B[k1](n,k1); else if(a>=c||b>=c){ int x=a/c,y=b/c; a%=c; b%=c; for(ll i=0,X=1; i<=k2; i++,X=(X*x)%Mod){ for(ll j=0,Y=X; i+j<=k2; j++,Y=Y*y%Mod){ ans=(ans+f(k1+i,k2-i-j,a,b,c,n,d+1)*C[k2][i]%Mod*C[k2-i][j]%Mod*Y%Mod)%Mod; } } }else{ int m=(a*n+b)/c; --m; ans=A[k2](m,k2); ans=ans*B[k1](n,k1)%Mod; for(int j=0; j

题目：
  • 【BZOJ3817-Sum】
  • 【大佬-Blog】
LOJ模板题的另外两个讲解：
  • zzq大佬的博客Orz
  • 大佬博客Orz
End

    推荐阅读


      上一篇：缘起缘灭

      下一篇：离线下载