• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces 1188B – Count Pairs(思维题)

开发技术 开发技术 4小时前 3次浏览

Codeforces 题面传送门 & 洛谷题面传送门

虽说是一个 D1B,但还是想了我足足 20min,所以还是写篇题解罢(

首先注意到这个式子里涉及两个参数,如果我们选择固定一个并动态维护另一个的决策,则相当于我们要求方程 (ax^3+bx^2+cx+dequiv kpmod{p}) 的根,而这是很难维护的,因此这个思路行不通。考虑 ((x+y)(x^2+y^2)) 的性质,我们考虑在前面添上一项 ((x-y)),根据初中数学 ((x-y)(x+y)(x^2+y^2)=x^4-y^4),因此 ((x+y)(x^2+y^2)=dfrac{x^4-y^4}{x-y}),因此我们即需求 (dfrac{a_i^4-a_j^4}{a_i-a_j}equiv kpmod{p})((i,j)) 个数,两边同乘 ((a_i-a_j)) 再移个项可得 (a_i^4-ka_iequiv a_j^4-ka_jpmod{p})map 维护即可,由于 (a_ine a_j),所以左边的分式肯定有意义。

虽说是个 *2300,但还是让我学到了许多,稍微总结一下吧:

  • 看到 (p)​ 是质数这样的条件,大部分情况都要用到某些数在 (bmod p) 意义下的逆元,极少数情况与二次剩余有关。
  • 看到序列中两两元素不同的条件,复杂度有可能与 (sumlimits_{i=1}^ndfrac{n}{a_i}) 有关,因为调和级数是 (nln n) 的,如 CF1553F。也有可能要用到 (a_i-a_j) 的逆元,如本题。
  • 如果我们要统计满足 (dfrac{X(i,j)}{Y(i,j)}equiv kpmod{p})((i,j)) 个数,并且 (X(i,j),Y(i,j)) 都可以写作 (na_i+ma_j) 的形式,那么把 (Y(i,j)) 乘到右边去统计起来会很方便,其他情况可以考虑向这种情况转化。注意特判 (Y(i,j)=0) 的情况。
const int MAXN=3e5;
int n,k,p,a[MAXN+5];map<int,int> t;
int calc(int x){return (1ll*x*x%p*x%p*x%p-1ll*k*x%p+p)%p;}
int main(){
	scanf("%d%d%d",&n,&p,&k);ll res=0;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) res+=t[calc(a[i])],t[calc(a[i])]++;
	printf("%lldn",res);
	return 0;
}

程序员灯塔
转载请注明原文链接:Codeforces 1188B – Count Pairs(思维题)
喜欢 (0)