专栏文章

题解：AT_abc402_g [ABC402G] Sum of Prod of Mod of Linear

wwwt100127
AT_abc402_g题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipgk5oj
此快照首次捕获于
2025/12/03 11:39
3 个月前
此快照最后确认于
2025/12/03 11:39
3 个月前
查看原文
第一篇黑体题解，好兴奋

题意

TT 组数据，给定 N,M,A,B1,B2N,M,A,B_1,B_2，求
∑i=0N−1[(Ai+B1) mod M][(Ai+B2) mod M]\sum_{i=0}^{N-1} \left[(Ai+B_1) \bmod M \right] \left[ (Ai+B_2) \bmod M \right]
其中 0≤A,B1,B2<M0 \le A,B_1,B_2 < M。

前置知识

类欧几里得算法

思路

显然 B1,B2B_1,B_2 等价，不妨设 B1≥B2B_1 \ge B_2（否则将两数交换）。
取模比较烦人，所以将原式化成：
∑i=0N−1[(Ai+B1)−M⌊Ai+B2M⌋][(Ai+B2)−M⌊Ai+B2M⌋]\sum_{i=0}^{N-1} \left[(Ai+B_1) - M \left \lfloor \frac{Ai+B_2}{M} \right \rfloor \right] \left[(Ai+B_2) - M \left \lfloor \frac{Ai+B_2}{M} \right \rfloor \right]
记
ai=⌊Ai+B1M⌋,bi=⌊Ai+B2M⌋a_i = \left \lfloor \frac{Ai+B_1}{M} \right \rfloor ,b_i=\left \lfloor \frac{Ai+B_2}{M} \right \rfloor
展开后就是：
∑i=0N−1(Ai+B1)(Ai+B2)−M∑i=0N−1(Ai+B1)bi−M∑i=0N−1(Ai+B2)ai+M2∑i=0N−1aibi\sum_{i=0}^{N-1}(Ai+B_1)(Ai+B_2) - M \sum_{i=0}^{N-1}(Ai+B_1)b_i - M \sum_{i=0}^{N-1}(Ai+B_2)a_i + M^2 \sum_{i=0}^{N-1} a_ib_i
第一个可以 O(1)O(1) 求出，中间两个算是类欧几里得的板子，我们只需要处理第四个式子就行了。
考虑如何用已知“凑”出 ∑i=0N−1aibi\sum_{i=0}^{N-1} a_ib_i。
于是你的眼睛无意间扫到了 0≤B1,B2<M0 \le B_1,B_2 < M 这个条件
也就是说，(ai−bi)(a_i-b_i) 的值只能为 00 或 11。
那么 ∑i=0N−1(ai−bi)(ai−bi−1)=0\sum_{i=0}^{N-1} (a_i-b_i)(a_i-b_i-1)= 0。
展开得：
∑i=0N−1aibi=12∑i=0N−1(ai2+bi2−ai+bi)\sum_{i=0}^{N-1} a_ib_i = \frac{1}{2} \sum_{i=0}^{N-1} (a_i^2+b_i^2-a_i+b_i)
同样可以用类欧几里得解决。
所以最终的答案：
Answer(N−1,M,A,B1,B2)=A2N(N+1)(2N+1)6+A(B1+B2)N(N+1)2+B1B2(N+1)−M[A×(h(A,B1,M,N)+h(A,B2,M,N))−B1×f(A,B2,M,N)−B2×f(A,B1,M,N)]+M22[g(A,B1,M,N)+g(A,B2,M,N)−f(A,B1,M,N)+f(A,B2,M,N)]Answer(N-1,M,A,B_1,B_2)= \frac{A^2N(N+1)(2N+1)}{6} + \frac{A(B_1+B_2)N(N+1)}{2} + B_1B_2(N+1) - M \left [ A \times (h(A,B_1,M,N) + h(A,B_2,M,N)) - B_1 \times f(A,B2,M,N) - B_2 \times f(A,B_1,M,N) \right] + \frac{M^2}{2} \left [g(A,B_1,M,N) + g(A,B_2,M,N) - f(A,B_1,M,N) + f(A,B_2,M,N) \right ]
其中：
f(A,B,M,N)=∑i=0N⌊Ai+BM⌋g(A,B,M,N)=∑i=0N⌊Ai+BM⌋2h(A,B,M,N)=∑i=0Ni⌊Ai+BM⌋f(A,B,M,N) = \sum_{i=0}^{N} \left \lfloor \frac{Ai+B}{M} \right \rfloor \\ g(A,B,M,N) = \sum_{i=0}^{N} \left \lfloor \frac{Ai+B}{M} \right \rfloor^2 \\ h(A,B,M,N) = \sum_{i=0}^{N} i \left \lfloor \frac{Ai+B}{M} \right \rfloor

代码

CPP
#include<bits/stdc++.h>
#define int __int128
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
	template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
	template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
	template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
} using namespace Memory_Love;
int n,m,a,b1,b2;

struct Node
{
	int f,g,h;
	Node(int F=0,int G=0,int H=0){f=F,g=G,h=H;}
};
namespace Euclid
{
	int Pow2(int x){return x*x;}
	Node solve(int a,int b,int c,int n)
	{
		int f,g,h;
		if(a==0)
		{
			f=b/c*(n+1);
			g=Pow2(b/c)*(n+1);
			h=b/c*n*(n+1)/2;
		}
		else
		if(a>=c || b>=c)
		{
			Node last=solve(a%c,b%c,c,n);
			f=(a/c*n*(n+1)/2+b/c*(n+1)+last.f);
			g=(n*(n+1)*(2*n+1)/6*Pow2(a/c)+(n+1)*Pow2(b/c)+(a/c)*(b/c)*n*(n+1)+2*(b/c)*last.f+2*(a/c)*last.h+last.g);
			h=((a/c)*n*(n+1)*(2*n+1)/6+(b/c)*n*(n+1)/2+last.h);
		}
		else
		{
			int m=(a*n+b)/c;
			Node last=solve(c,c-b-1,a,m-1);
			f=(n*m-last.f);
			g=(n*m*(m+1)-f-2*(last.h+last.f));
			h=(n*m*(n+1)-last.g-last.f)/2;
		}
		return (Node){f,g,h};
	}
}

int solve()
{
	read(n,m,a,b1,b2);
	n--; if(b1<b2) swap(b1,b2);
	Node P1=Euclid::solve(a,b1,m,n);
	Node P2=Euclid::solve(a,b2,m,n);
	int ans1=a*a*n*(n+1)*(2*n+1)/6;
	int ans2=a*(b1+b2)*n*(n+1)/2;
	int ans3=(n+1)*b1*b2;
	int ans4=m*(a*(P1.h+P2.h)+b1*P2.f+b2*P1.f);
	int ans5=m*m*(P1.g+P2.g-P1.f+P2.f)/2;
	return ans1+ans2+ans3-ans4+ans5;
}

bool Ending;
signed main()
{
	int T=read(); while(T--) write(solve(),'\n');
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...