2020-2021:teams:legal_string:王智彪:类欧几里得算法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:类欧几里得算法 [2021/08/17 09:39] 王智彪 |
2020-2021:teams:legal_string:王智彪:类欧几里得算法 [2021/08/17 11:32] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 76: | 行 76: | ||
| 先设 $f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$ | 先设 $f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$ | ||
| - | |||
| - | \lfloor {\frac a c} \rfloor | ||
| 1.求 $g(a,b,c,n)=\sum_{i=0}^{n}{\lfloor {\frac {ai+b} c} \rfloor}^{2}$ 和 $h(a,b,c,n)=\sum_{i=0}^{n}i \lfloor {\frac {ai+b} {c}} \rfloor$ | 1.求 $g(a,b,c,n)=\sum_{i=0}^{n}{\lfloor {\frac {ai+b} c} \rfloor}^{2}$ 和 $h(a,b,c,n)=\sum_{i=0}^{n}i \lfloor {\frac {ai+b} {c}} \rfloor$ | ||
| 行 111: | 行 109: | ||
| $=nm(m+1)-f(a,b,c,n)-2h(c,-b-1,a,m)$ | $=nm(m+1)-f(a,b,c,n)-2h(c,-b-1,a,m)$ | ||
| + | $h(a,b,c,n)=\sum_{i=0}^{n}i\sum_{j=1}^{m}[j≤\lfloor {\frac {ai+b} {c}} \rfloor]$ | ||
| + | |||
| + | $=\sum_{i=0}^{n}i\sum_{j=0}^{m-1}[(j+1)c＜ai+b+1]$ | ||
| + | |||
| + | $=\sum_{j=0}^{m-1}\sum_{i=0}^{n}i[i＞{\frac {jc+c-b-1} {a}}]$ | ||
| + | |||
| + | $=\sum_{j=0}^{m-1}({\frac {n(n+1)} {2}}-\sum_{i=0}^{n}i[i≤{\lfloor {\frac {jc+c-b-1} {a}} \rfloor}])$ | ||
| + | |||
| + | $=\sum_{j=0}^{m-1}({\frac {n(n+1)} {2}}-{\frac {{\lfloor {\frac {jc+c-b-1} {a}} \rfloor}(\lfloor {\frac {jc+c-b-1} {a}} \rfloor+1)} {2}})$ | ||
| + | |||
| + | $={\frac {\sum_{j=0}^{m-1}n(n+1)-\sum_{j=0}^{m-1}{\lfloor {\frac {jc+c-b-1} {a}} \rfloor}^{2}-\sum_{j=0}^{m-1}{\lfloor {\frac {jc+c-b-1} {a}} \rfloor}} {2}}$ | ||
| + | |||
| + | $={\frac 1 2}[mn(n+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)]$ | ||
| + | |||
| + | 注意负数那里会导致计算错误，比如 ${\frac {-1} 2}={\frac {1} 2}=0$ | ||
| + | |||
| + | 所以在实际计算中，要规避掉参数为负的情况，这个具体情况具体分析。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const ll mod=998244353,inv2=(mod+1)>>1,inv3=332748118; | ||
| + | |||
| + | struct Ans { | ||
| + | ll f,s,t; | ||
| + | }ans,now,las; | ||
| + | Ans getans(int a,int b,int c,int n) { | ||
| + | if(!a) { | ||
| + | now.f=(ll)b/c*(n+1)%mod; | ||
| + | now.s=(ll)(b/c)*(b/c)%mod*(n+1)%mod; | ||
| + | now.t=((ll)n+1)*n/2%mod*(b/c)%mod; | ||
| + | } | ||
| + | else if(a>=c||b>=c) { | ||
| + | las=getans(a%c,b%c,c,n); | ||
| + | now.f=(((ll)n*(n+1)/2%mod*(a/c)%mod+((ll)n+1)*(b/c)%mod)%mod+las.f)%mod; | ||
| + | ll tmp1=((las.s+2ll*(a/c)%mod*las.t%mod)%mod+2ll*(b/c)%mod*las.f%mod)%mod; | ||
| + | ll tmp2=(((ll)n*(n+1)%mod*(2ll*n+1)%mod*inv2%mod*inv3%mod*(a/c)%mod*(a/c)%mod+(ll)n*(n+1)%mod*(a/c)%mod*(b/c)%mod)%mod+(ll)(n+1)*(b/c)%mod*(b/c)%mod)%mod; | ||
| + | now.s=(tmp1+tmp2)%mod; | ||
| + | now.t=(((ll)n*(n+1)/2%mod*(b/c)%mod+((ll)n+1)*n%mod*inv2%mod*((ll)n*2+1)%mod*inv3%mod*(a/c)%mod)%mod+las.t)%mod; | ||
| + | }else { | ||
| + | ll m=((ll)a*n+b)/c; | ||
| + | las=getans(c,c-b-1,a,m-1); | ||
| + | now.f=((ll)n*m%mod-las.f+mod)%mod; | ||
| + | now.s=((ll)n*m%mod*(m+1)%mod-now.f+mod-2ll*las.t%mod+mod-2ll*las.f%mod+mod)%mod; | ||
| + | now.t=((ll)m*n%mod*(n+1)%mod-las.f+mod-las.s+mod)%mod*inv2%mod; | ||
| + | } | ||
| + | return now; | ||
| + | } | ||
| + | int n,a,b,c; | ||
| + | int main() { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | while(t--) { | ||
| + | scanf("%d %d %d %d",&n,&a,&b,&c); | ||
| + | ans=getans(a,b,c,n); | ||
| + | printf("%lld %lld %lld\n",ans.f,ans.s,ans.t); | ||
| + | //printf("%lld %lld %lld\n",f(a,b,c,n),g(a,b,c,n),h(a,b,c,n)); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | /* | ||
| + | 10 | ||
| + | 7 7 7 7 | ||
| + | 8 0 10 4 | ||
| + | 8 2 4 3 | ||
| + | 3 4 5 3 | ||
| + | 0 3 10 1 | ||
| + | 1 0 0 7 | ||
| + | 3 9 10 1 | ||
| + | 8 5 5 4 | ||
| + | 5 4 0 9 | ||
| + | 10 4 4 9 | ||
| + | */ | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | $ps$ ：这里一起计算是因为，单独记忆化 $t$ 了... | ||
2020-2021/teams/legal_string/王智彪/类欧几里得算法.1629164364.txt.gz · 最后更改: 2021/08/17 09:39 由 王智彪
