【CodeChef NTHCIR】Rohith and Circles（线性递推）（圆的反演）

传送门

---

题解：

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

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

设 $a_1=-1/r_1,a_i=1/r_i$a1​=−1/r1​,ai​=1/ri​，则 $(a_1+a_2+a_{n-1}+a_{n})^2=a_1^2+a_2^2+a_{n-1}^2+a_{n}^2$(a1​+a2​+an−1​+an​)2=a12​+a22​+an−12​+an2​

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

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

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

$a_{n}+a_{n-2}=2(a_1+a_2+a_{n-1})$an​+an−2​=2(a1​+a2​+an−1​)

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

进行一次差分可以得到 $a_n-3a_{n-1}+3a_{n-2}-a_{n-3}=0$an​−3an−1​+3an−2​−an−3​=0，特征方程为 $(x-1)^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;}