求 ∑ i = 0 n ⌊ a i + b c ⌋ \sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor i=0∑n⌊cai+b⌋
推式子步骤:
分类讨论
a = 0 a=0 a=0
是个最简式子
b ≥ c b\ge c b≥c 或 a ≥ c a\ge c a≥c
由 f ( a m o d c , b m o d c , c , n ) f(a\bmod c,b\bmod c,c,n) f(amodc,bmodc,c,n) 转移过来,拆一下括号就行
其他情况
设 M = ⌊ a n + b c ⌋ M=\lfloor\frac{an+b}{c}\rfloor M=⌊can+b⌋
⌊ a i + b c ⌋ = ∑ j = 1 M [ j ≤ ⌊ a i + b c ⌋ ] \lfloor \frac{ai+b}{c} \rfloor=\sum_{j=1}^M [j\le\lfloor\frac{ai+b}{c}\rfloor] ⌊cai+b⌋=∑j=1M[j≤⌊cai+b⌋]
- 拆一下后面的除号
- 把所有 j j j 变成 j − 1 j-1 j−1
- 交换求和顺序
- 变成 i > x i>x i>x 的形式
- 变成 n − i ≤ x n-i\le x n−i≤x 的形式
- 后面直接换成 f ( c , c − b − 1 , a , m − 1 ) f(c,c-b-1,a,m-1) f(c,c−b−1,a,m−1)
int floor_sum(int n, int c, int a, int b) {
if(a==0) return (n+1)*(b/c);
if(a>=c || b>=c)
return floor_sum(n, c, a%c, b%c)+n*(n+1)/2*(a/c)+(n+1)*(b/c);
int m=(a*n+b)/c;
return n*m-floor_sum(m-1, a, c, c-b-1);
}
对于 ∑ i = 0 n ⌊ a i + b c ⌋ 2 , ∑ i = 0 n i ⌊ a i + b c ⌋ \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\ \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor i=0∑n⌊cai+b⌋2, i=0∑ni⌊cai+b⌋ 的求解
推的方法类似,不过会互相调用
node floor_sum(int a, int b, int c, int n) {
if(a==0) return {
(n+1)*(b/c)%p, (n+1)*(b/c)%p*(b/c)%p, n*(n+1)%p*i2%p*(b/c)%p};
if(a>=c || b>=c) {
node t=floor_sum(a%c, b%c, c, n);
int F=t.f+n*(n+1)%p*i2%p*(a/c)%p+(n+1)*(b/c)%p;
int G=t.g+2*t.h%p*(a/c)%p+2*(b/c)%p*t.f%p+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p*(a/c)%p+(n+1)*n%p*(a/c)%p*(b/c)%p+(n+1)*(b/c)%p*(b/c)%p;
int H=t.h+n*(n+1)%p*(2*n+1)%p*i6%p*(a/c)%p+n*(n+1)%p*i2%p*(b/c)%p;
return {
F%p, G%p, H%p};
}
int m=(a*n+b)/c;
node t=floor_sum(c, c-b-1, a, m-1);
int F=n*m%p-t.f;
int G=n*m%p*(m+1)%p-2*t.f%p-2*t.h%p-F;
int H=(m*n%p*(n+1)%p-t.g-t.f)%p*i2%p;
return {
F%p, G%p, H%p};
}