首页 > 代码库 > BZOJ 4815: [Cqoi2017]小Q的表格
BZOJ 4815: [Cqoi2017]小Q的表格
Description
\(b×f(a,a+b)=(a+b)*f(a,b)\),支持修改
求\(\sum_{i=1}^k\sum_{j=1}^kf(i,j)\)
\(m\leqslant 10^4,k\leqslant n\leqslant 4\times 10^6\)
Solution
数论+分块
可以发现这是一个类似于更相减损的东西...
就是修改一个位置,只会影响与他横纵坐标相同的位置...所以它其实是一个一维的东西...
所以就是求\(\sum_{i=1}^k\sum_{j=1}^k\frac{f[(i,j)]*(i,j)^2}{ij}\)
求这个东西可以数论的分块...维护就是普通的分块...
Code
/************************************************************** Problem: 4815 User: BeiYu Language: C++ Result: Accepted Time:17544 ms Memory:188816 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 4e6+500;const int B = 2000;const LL p = 1000000007; inline LL in(LL x=0,char ch=getchar()) { while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();return x; }void Add(LL &x,LL y) { x=(x+y)%p; }LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; } LL n,m,ans,inv_6=Pow(6,p-2);LL f[N],g[N];int pr[N],cp,b[N],phi[N];int tb,bl[N],ll[N],rr[N];LL tg[N]; void pre(int n) { for(int i=2;i<=n;i++) { if(!b[i]) pr[++cp]=i,phi[i]=i-1; for(int j=1;j<=cp && (LL)i*pr[j]<=n;j++) { b[i*pr[j]]=1; if(i%pr[j]) phi[i*pr[j]]=phi[i]*(pr[j]-1); else { phi[i*pr[j]]=phi[i]*pr[j];break; } } }phi[1]=1; for(int i=1;i<=n;i++) g[i]=(1LL*phi[i]*i%p*i%p+g[i-1])%p;} LL get_s1(LL n) { return (n*(n+1)/2)%p; }LL get_s2(LL n) { return n*(n+1)%p*(2*n+1)%p*inv_6%p; } void Mot(int x,LL v) { for(int i=x;i<=rr[bl[x]];i++) Add(f[i],v); for(int i=bl[x]+1;i<=tb;i++) Add(tg[i],v);}LL Qur(int x) { return (f[x]+tg[bl[x]])%p; }LL A(int n) { LL res=0; for(int i=1,j;i<=n;i=j+1) { j=n/(n/i); Add(res,(Qur(j)-Qur(i-1)+p)%p*g[n/i]%p); }return res;} int main() { m=in(),n=in(); pre(n); for(int i=1;i<=n;i++) f[i]=(1LL*i*i%p+f[i-1])%p; for(int i=1;i<=n;i+=B) { tb++,ll[tb]=i,rr[tb]=min((LL)i+B-1,n); for(int j=0;j<B && i+j<=n;j++) bl[i+j]=tb; } for(int i=1;i<=m;i++) { LL x=in(),y=in(),z=in(),k=in(),w=__gcd(x,y); z=z/(x/w)/(y/w)%p; Mot(w,(z-(f[w]-f[w-1]+p)%p+p)%p); printf("%lld\n",A(k)); }return 0;}
BZOJ 4815: [Cqoi2017]小Q的表格
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。