模板
传送门
由于太懒以下直接用 a / b 表 示 ? a b ? a/b表示\lfloor \frac a b\rfloor a/b表示?ba??
如果有乘除叠一起会单独打括号区分乘除的地方
1 、 f ： 1、f： 1、f：
求 f ( a , b , c , n ) = ∑ i = 0 n ( a i + b ) / c f(a,b,c,n)=\sum_{i=0}^n(ai+b)/c f(a,b,c,n)=∑i=0n?(ai+b)/c
当 a = 0 a=0 a=0时
f = ( n + 1 ) ( b / c ) f=(n+1)(b/c) f=(n+1)(b/c)
否则若有 a ≥ c ∣ ∣ b ≥ c a\geq c ||b\geq c a≥c∣∣b≥c
f = ∑ i = 0 n ( i a % c + b % c ) / c + i ( a / c ) + ( b / c ) f=\sum_{i=0}^{n}(ia\%c+b\%c)/c+i(a/c)+(b/c) f=i=0∑n?(ia%c+b%c)/c+i(a/c)+(b/c)
= f ( a % c , b % c , c , n ) + n ? ( n + 1 ) / 2 ? ( a / c ) + ( n + 1 ) ( b / c ) =f(a\%c,b\%c,c,n)+n*(n+1)/2*(a/c)+(n+1)(b/c) =f(a%c,b%c,c,n)+n?(n+1)/2?(a/c)+(n+1)(b/c)
当 a < c a 令 m = ( a n + b ) / c m=(an+b)/c m=(an+b)/c
f = ∑ i = 0 n ∑ j = 1 m [ j ≤ ( a i + b ) / c ] f=\sum_{i=0}^n\sum_{j=1}^{m}[j\le(ai+b)/c] f=i=0∑n?j=1∑m?[j≤(ai+b)/c]
f = ∑ i = 0 n ∑ j = 0 m ? 1 [ j + 1 < ( a i + b + 1 ) / c ] f=\sum_{i=0}^n\sum_{j=0}^{m-1}[j+1<(ai+b+1)/c] f=i=0∑n?j=0∑m?1?[j+1<(ai+b+1)/c]
= ∑ i = 0 n ∑ j = 0 m ? 1 [ i > ( j c + c ? b ? 1 ) / a ] =\sum_{i=0}^n\sum_{j=0}^{m-1}[i>(jc+c-b-1)/a] =i=0∑n?j=0∑m?1?[i>(jc+c?b?1)/a]
= ∑ j = 0 m ? 1 ∑ i = 0 n [ i > ( j c + c ? b ? 1 ) / a ] =\sum_{j=0}^{m-1}\sum_{i=0}^n[i>(jc+c-b-1)/a] =j=0∑m?1?i=0∑n?[i>(jc+c?b?1)/a]
= ∑ j = 0 m ? 1 n ? ( j c + c ? b ? 1 ) / a =\sum_{j=0}^{m-1}n-(jc+c-b-1)/a =j=0∑m?1?n?(jc+c?b?1)/a
= n m ? f ( c , c ? b ? 1 , a , m ? 1 ) =nm-f(c,c-b-1,a,m-1) =nm?f(c,c?b?1,a,m?1)
显然复杂度为 O ( l o g n ) O(logn) O(logn)
2 : g , h 2:g,h 2:g,h
求 g ( a , b , c , n ) = ∑ i = 0 n ( ( a i + b ) / c ) 2 g(a,b,c,n)=\sum_{i=0}^n((ai+b)/c)^2 g(a,b,c,n)=∑i=0n?((ai+b)/c)2
h ( a , b , c , n ) = ∑ i = 0 n i ( ( a i + b ) / c ) h(a,b,c,n)=\sum_{i=0}^ni((ai+b)/c) h(a,b,c,n)=∑i=0n?i((ai+b)/c)
首先类似
a = 0 a=0 a=0时
g = ( n + 1 ) ( b / c ) 2 , h = n ? ( n + 1 ) / 2 ? ( b / c ) g=(n+1)(b/c)^2,h=n*(n+1)/2*(b/c) g=(n+1)(b/c)2,h=n?(n+1)/2?(b/c)
当 a ≥ c ∣ ∣ b ≥ c a\geq c||b\geq c a≥c∣∣b≥c时
类似之前 f f f
拆开得到
g = g ( a % c , b % c , c , n ) + 2 ? ( a / c ) ? h ( a % c , b % c , c , n ) + 2 ? ( b / c ) ? f ( a % c , b % c , c , n ) + ( a / c ) ? ( b / c ) ? n ? ( n + 1 ) + n ? ( n + 1 ) ? ( 2 n + 1 ) / 6 ? ( a / c ) 2 + ( n + 1 ) ? ( b / c ) 2 g=g(a\%c,b\%c,c,n)+2*(a/c)*h(a\%c,b\%c,c,n)+2*(b/c)*f(a\%c,b\%c,c,n)\\+(a/c)*(b/c)*n*(n+1)+n*(n+1)*(2n+1)/6*(a/c)^2+(n+1)*(b/c)^2 g=g(a%c,b%c,c,n)+2?(a/c)?h(a%c,b%c,c,n)+2?(b/c)?f(a%c,b%c,c,n)+(a/c)?(b/c)?n?(n+1)+n?(n+1)?(2n+1)/6?(a/c)2+(n+1)?(b/c)2
h = h ( a % c , b % c , c , n ) + n ? ( n + 1 ) ? ( 2 n + 1 ) / 6 ? ( a / c ) + n ? ( n + 1 ) / 2 ? ( b / c ) h=h(a\%c,b\%c,c,n)+n*(n+1)*(2n+1)/6*(a/c)+n*(n+1)/2*(b/c) h=h(a%c,b%c,c,n)+n?(n+1)?(2n+1)/6?(a/c)+n?(n+1)/2?(b/c)
当 a < c a 设 m = ( a n + b ) / c m=(an+b)/c m=(an+b)/c
g = ∑ i = 0 n ( ( a i + b ) / c ) 2 g=\sum_{i=0}^n((ai+b)/c)^2 g=i=0∑n?((ai+b)/c)2
= 2 ? ∑ i = 0 n ∑ j = 1 ( a i + b ) / c j ? ∑ i = 0 n ( a i + b ) / c = ? f ( a , b , c , n ) + 2 ∑ i = 0 n ∑ j = 0 m ? 1 ( j + 1 ) [ j c + c < a i + b + 1 ] = ? f + 2 ∑ j = 0 m ? 1 ( j + 1 ) [ i > ( j c + c ? b ? 1 ) / a ] = ? f + 2 ∑ j = 0 m ? 1 ( j + 1 ) ( n ? ( j c + c ? b ? 1 ) / a ) = ? f ( a , b , c , n ) + m ( m + 1 ) n ? 2 f ( c , c ? b ? 1 , a , m ? 1 ) ? 2 h ( c , c ? b ? 1 , a , m ? 1 ) =2*\sum_{i=0}^n\sum_{j=1}^{(ai+b)/c}j-\sum_{i=0}^n(ai+b)/c\\ =-f(a,b,c,n)+2\sum_{i=0}^n\sum_{j=0}^{m-1}(j+1)[jc+c(jc+c-b-1)/a]\\ =-f+2\sum_{j=0}^{m-1}(j+1)(n-(jc+c-b-1)/a)\\ =-f(a,b,c,n)+m(m+1)n-2f(c,c-b-1,a,m-1)-2h(c,c-b-1,a,m-1) =2?i=0∑n?j=1∑(ai+b)/c?j?i=0∑n?(ai+b)/c=?f(a,b,c,n)+2i=0∑n?j=0∑m?1?(j+1)[jc+c(jc+c?b?1)/a]=?f+2j=0∑m?1?(j+1)(n?(jc+c?b?1)/a)=?f(a,b,c,n)+m(m+1)n?2f(c,c?b?1,a,m?1)?2h(c,c?b?1,a,m?1)
h = ∑ i = 0 n i ( ( a i + b ) / c ) = ∑ i = 0 n i ∑ j = 0 m ? 1 [ i > ( j c + c ? b ? 1 ) / a ] = ∑ j = 0 m ? 1 ∑ i = 0 n i [ i > ( j c + c ? b ? 1 ) / a ] = m ? n ? ( n + 1 ) / 2 ? ∑ j = 0 m ? 1 ∑ i = 0 n i [ i ≤ ( j c + c ? b ? 1 ) / a ] = m ? n ? ( n + 1 ) / 2 ? ∑ j = 0 m ? 1 ∑ i = 0 ( j c + c ? b ? 1 ) / a i = m ? n ? ( n + 1 ) / 2 ? ∑ j = 0 m ? 1 ( ( j c + c ? b ? 1 ) / a ) ? ( ( j c + c ? b ? 1 ) / a + 1 ) / 2 = 1 2 ( m ? n ? ( n + 1 ) ? ∑ i = 0 m ? 1 ( ( j c + c ? b ? 1 ) / a ) 2 ? ∑ i = 0 m ? 1 ( ( j c + c ? b ? 1 ) / a ) ) = 1 2 ( m ? n ? ( n + 1 ) ? f ( c , c ? b ? 1 , a , m ? 1 ) ? g ( c , c ? b ? 1 , a , m ? 1 ) ) h=\sum_{i=0}^ni((ai+b)/c)\\ =\sum_{i=0}^ni\sum_{j=0}^{m-1}[i>(jc+c-b-1)/a]\\ =\sum_{j=0}^{m-1}\sum_{i=0}^ni[i>(jc+c-b-1)/a]\\ =m*n*(n+1)/2-\sum_{j=0}^{m-1}\sum_{i=0}^ni[i\le(jc+c-b-1)/a]\\ =m*n*(n+1)/2-\sum_{j=0}^{m-1}\sum_{i=0}^{(jc+c-b-1)/a}i\\ =m*n*(n+1)/2-\sum_{j=0}^{m-1}((jc+c-b-1)/a)*((jc+c-b-1)/a+1)/2\\ =\frac 1 2(m*n*(n+1)-\sum_{i=0}^{m-1}((jc+c-b-1)/a)^2-\sum_{i=0}^{m-1}((jc+c-b-1)/a))\\ =\frac 1 2(m*n*(n+1)-f(c,c-b-1,a,m-1)-g(c,c-b-1,a,m-1)) h=i=0∑n?i((ai+b)/c)=i=0∑n?ij=0∑m?1?[i>(jc+c?b?1)/a]=j=0∑m?1?i=0∑n?i[i>(jc+c?b?1)/a]=m?n?(n+1)/2?j=0∑m?1?i=0∑n?i[i≤(jc+c?b?1)/a]=m?n?(n+1)/2?j=0∑m?1?i=0∑(jc+c?b?1)/a?i=m?n?(n+1)/2?j=0∑m?1?((jc+c?b?1)/a)?((jc+c?b?1)/a+1)/2=21?(m?n?(n+1)?i=0∑m?1?((jc+c?b?1)/a)2?i=0∑m?1?((jc+c?b?1)/a))=21?(m?n?(n+1)?f(c,c?b?1,a,m?1)?g(c,c?b?1,a,m?1))
【【模板】类欧几里得】复杂度 O ( l o g n ) O(logn) O(logn)
万能欧几里得
传送门
求 ∑ i = 1 l A i B ( p i + r ) / q \sum_{i=1}^lA^iB^{(pi+r)/q} ∑i=1l?AiB(pi+r)/q
考虑这样一个操作
维护一个三元组 a , b , s a,b,s a,b,s
考虑一条线段 y = ( p x + r ) / q y=(px+r)/q y=(px+r)/q
在 ( 0 , L ] (0,L] (0,L]内从左往右走
每当线段碰到 x = c x=c x=c时令 a = a ? A a=a*A a=a?A
每当碰到 y = c y=c y=c时令 b = b ? B b=b*B b=b?B
对于整点先进行 y = c y=c y=c再进行 x = c x=c x=c
每次操作后令 n e ws = s + A ? B new \ s=s+A*B new s=s+A?B
显然这和原来求得东西等价
观察到这是一个线性变换，拥有结合律
万能欧几里得能利用压缩信息在 O ( l o g T ( n ) ) O(logT(n)) O(logT(n))的时间求出这个东西
考虑当 r ≥ q r\geq q r≥q时令 r = r % q r=r\%q r=r%q不会对操作序列产生影响
只是初始的 b b b会变成 b r / q b^{r/q} br/q，先做即可
设函数为 f ( p , q , r , l , a , b ) f(p,q,r,l,a,b) f(p,q,r,l,a,b)
当 p ≥ q p\geq q p≥q时
设 k = ( p / q ) k=(p/q) k=(p/q)
那么考虑线段为 y = k x + ( ( p % q ) x + r ) / q y=kx+((p\%q)x+r)/q y=kx+((p%q)x+r)/q
那么每次 x x x加一前必定会至少有 k k k次 y y y的变化
于是可以直接递归 f ( p % q , q , r , l , b k ? a , b ) f(p\%q,q,r,l,b^{k}*a,b) f(p%q,q,r,l,bk?a,b)
否则考虑可以翻转坐标轴,将 x , y x,y x,y反过来
翻转后的函数就是反函数
为 x = ( q y ? r ) / p x=(qy-r)/p x=(qy?r)/p
但是这时候如果按照原来的在整点时候的计算顺序就反了
于是考虑变成 x = ( q y ? r ? 1 ) / p x=(qy-r-1)/p x=(qy?r?1)/p强制先计算 x x x
设 k = ( p l + r ) / q k=(pl+r)/q k=(pl+r)/q
考虑翻转后求 y ∈ ( 1 , k ] y\in(1,k] y∈(1,k]范围内的
那显然要先把前面没计算的部分求了
就是 a ( q ? r ? 1 ) / p ? b a^{(q-r-1)/p}*b a(q?r?1)/p?b
考虑把 y ∈ ( 1 , k ] → y ∈ ( 0 , k ? 1 ] y\in(1,k]\rightarrow y\in(0,k-1] y∈(1,k]→y∈(0,k?1]
那么函数就变成 x = ( q y + q ? r ? 1 ) / p x=(qy+q-r-1)/p x=(qy+q?r?1)/p
于是递归 f ( q , p , q ? r ? l , k ? 1 , b , a ) f(q,p,q-r-l,k-1,b,a) f(q,p,q?r?l,k?1,b,a)
但是 k k k之后可能还有一些 x x x没被计算到
个数是 l ? ( k q ? r ? 1 ) / p l-(kq-r-1)/p l?(kq?r?1)/p
于是在后面乘上一个 a l ? ( k q ? r ? 1 ) / p a^{l-(kq-r-1)/p} al?(kq?r?1)/p即可
复杂度应该是 O ( n 3 l o g ) O(n^3log) O(n3log)

#include using namespace std; #define cs const #define re register #define pb push_back #define pii pair #define ll long long #define fi first #define se second #define bg begin cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0; bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } inline ll readll(){ char ch=gc(); ll res=0; bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } inline int readstring(char *s){ int top=0; char ch=gc(); while(isspace(ch))ch=gc(); while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc(); return top; } templateinline void chemx(tp &a,tp b){ainline void chemn(tp &a,tp b){a>b?a=b:0; } cs int mod=998244353; inline int add(int a,int b){return (a+=b)>=mod?(a-mod):a; } inline int dec(int a,int b){a-=b; return a+(a>>31&mod); } inline int mul(int a,int b){static ll r; r=1ll*a*b; return (r>=mod)?(r%mod):r; } inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0; } inline void Dec(int &a,int b){a-=b,a+=a>>31&mod; } inline void Mul(int &a,int b){static ll r; r=1ll*a*b; a=(r>=mod)?(r%mod):r; } inline int ksm(int a,int b,int res=1){if(a==0&&b==0)return 0; for(; b; b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1); return res; } inline int Inv(int x){return ksm(x,mod-2); } inline int fix(ll x){return x%=mod,(x<0)?x+mod:x; } int n; struct mat{ int a[21][21]; mat(){memset(a,0,sizeof(a)); } friend inline mat operator *(cs mat &a,cs mat &b){ mat c; for(int i=0; i>=1,x=x*x)if(b&1)res=res*x; return res; } }; node solve(ll p,ll q,ll r,ll l,cs node &a,cs node &b){ if(l==0)return node(I,I,O); r%=q; if(p>=q)return solve(p%q,q,r,l,(b^(p/q))*a,b); ll k=((long double)p*l+r)/q; if(k==0)return a^l; ll v=((long double)k*q-r-1)/p; v=l-v; return (a^((q-r-1)/p))*b*solve(q,p,q-r-1,k-1,b,a)*(a^v); } ll p,q,r,l; int main(){ #ifdef Stargazer freopen("lx.in","r",stdin); #endif p=readll(),q=readll(),r=readll(),l=readll(),n=read(); for(int i=0; i