【CodeChef NTHCIR】Rohith and Circles（线性递推）（圆的反演）传送门题解：

104 阅读 0 评论 69 点赞

我是靠谱客的博主动听魔镜，最近开发中收集的这篇文章主要介绍【CodeChef NTHCIR】Rohith and Circles（线性递推）（圆的反演）传送门题解：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

题解：

圆的反演做法比较明显，直接把 $C_1$ 和 $C_2$ 的交点作为反演点，那么 $C_1$ 和 $C_2$ 反演出来就是两条平行直线，把后面的圆一个个放进去就行了。

不过也可以做得简单一点，利用笛卡尔定理：here。

设 $a_1=-1/r_1,a_i=1/r_i$ ，则 $a_1+a_2+a_{n-1}+a_{n})^2=a_1^2+a_2^2+a_{n-1}^2+a_{n}^2$

很容易注意到其实每个 $a_n$ 有两个解，这显然对应着下一个圆放在两边的情况。

解的形式可以表示为： $a_n=a_1+a_2+a_{n-1}pm 2sqrt{a_1a_2+(a_1+a_2)a_{n-1}}$

右边式子中的正负号分别对应着 $a_n$ 和 $a_{n-2}$ ，于是很显然地，我们可以得到：

$a_{n}+a_{n-2}=2(a_1+a_2+a_{n-1})$

得到一个二阶线性非齐次递推式： $a_n=2a_{n-1}-a_{n-2}+c$ ，其中 $c=2(a_1+a_2)$

进行一次差分可以得到 $a_n-3a_{n-1}+3a_{n-2}-a_{n-3}=0$ ，特征方程为 $x-1)^3=0$ ，按照常规搞递推式的方式搞就行了。

不过有一个问题，答案炸long double，考虑这组数据：

10000000
1 2 1 1
99999999999.999999 r2 r3 r4

这样每次都是询问第一个圆，答案应该是 999999999999999990。这个炸long double了。。。

出题人可能就没想过这种。

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const
int T,n,p,m,b;
double r1,r2,r3,r4,ans,res,a1,a2,a3,a4;
void Main(){
scanf("%d%d%d%d%d",&T,&n,&p,&m,&b);
scanf("%lf%lf%lf%lf",&r1,&r2,&r3,&r4);
a1=-1/r1,a2=1/r2,a3=1/r3,a4=1/r4;
double C1=a4-a3-7*(a1+a2);
double C2=a3-9*(a1+a2)-3*C1;
while(T--)switch(n=(ll)n*p%m+b){
case 1:ans+=r1;break;
case 2:ans+=r2;break;
case 3:ans+=r3;break;
case 4:ans+=r4;break;
default:ans+=1/((a1+a2)*n*n+C1*n+C2);
}printf("%.6lf",ans);
}
void file(){
#ifdef zxyoi
freopen("nthcir.in","r",stdin);
//	freopen("nthcir.out","w",stdout);
#endif
}
signed main(){file();Main();return 0;}