Codechef July Challenge 2015 » NTHCIR

虽然我知道在比赛还没结束前挂题解不好，但是还是想骗一发访问量。

题目大概是这样的：

有很多圆，满足 $C_n(n\ge 4)$ 与 $C_1,C_2,\cdots ,C_{n-1}$ 都相切，$C_3$ 与 $C_1,C_2$ 相切，$C_2$ 与 $C_1$ 相切，图形如下：

现已知 $r_1,r_2,r_3,r_4$，求 $r_n$。询问数<=1000w，$n\le {10}^9$，时限 $1.5s$

例如：当 $r_1=6,r_2=r_3=3,r_4=2$ 的时候，圆大概长这样：

圆的反演是什么呢？

我们先选定一个点 $O$为反演中心，以 $O$ 为圆心，半径为 $r$ 画一个圆。然后对于平面上的点 $P$ 和 $P^{\prime }$，如果 $P$ 和 $P^{\prime }$ 在以 $O$ 为起点的射线上，并且 $|OP|\cdot |O{P}^{\prime }|=r^2$，那么就说 $P$ 和 $P^{\prime }$ 互为反演点。

所以圆外的点反演一下会到圆内，圆内会到圆外，圆上则不变。

我找了 $GeoGebra$ 来玩玩，效果差不多是长下面这个样子的：

反演中心为坐标原点，点 $H$ 在直线上移动，点 $J$ 为射线 $AH$的焦点，点 $I$ 为点 $H$ 的反演点。

可以看到，一条不过反演中心的直线反演之后变成了一个过反演中心的圆。而且直线和两个圆两两相交。

由于反演的可逆性，这个圆反演一下就变成了一条直线啦~

一个不过反演中心的圆反演以后是一个以反演中心位似的圆。

从上面的图来看，显然两个圆是反过来对应的，并不是直接位似。还有切记，圆心反演完以后并不是反演完的圆的圆心，比如上面的点 $H$ 和 $I$。

再来一个好玩点的：

抛物线反演一下，不知道变成了什么。。。右边的黑线是 $2\sqrt{x}$，然而不能拟合。

然后稍微往下移一点就变成了心型线！

椭圆好像跟上面两种差不多，不是太好玩。

双曲线反演一下变成了 $\mathrm{\infty }$...

我们不妨把样例反演一下变成下面这样：

由于反演前后的几何性质是不会发生改变的，比如反演前两个圆相切，反演完以后他们两个还是相切，只不过可能不是圆与圆相切而是直线与圆相切之类的，因此我们可以像这张图这样建立反演中心，圆 $C_1,C_2$ 反演完以后就变成了两条直线，而 $C_3,C_4,\cdots$ 反演完之后，由于没过反演中心，所以还是圆；又因为它们都与圆 $C_1,C_2$ 相切，所以反演以后的圆统统都被夹在了两条直线里面，大小都一样，而且一个挨着一个。

这里详细讲了怎么求一个圆的反演

然而我觉得如果不会求的话，可以随便找圆上的三个点，然后把这三个点反一下，然后再以这三个点画个圆就好了，简单粗暴= =

注意不能直接求圆心。原因在上面第二张截屏。

于是这题的解法已经十分明了了：先把 $C_1,C_2$ 反成直线，解三角形解出 $C_3$ 的位置，然后反成小圆，看一下 $C_4$ 塞哪里符合题意，然后就可以 $O(1)$ 求出第 $n$ 个圆反演完以后的圆，直接反回去就好了。

本题按时间复杂度的不同共有三种解法。

Sol-1 $O(m^{2}log(n))$

令 $f(n,k)=\sum _{i=1}^n{i}^k\cdot m^i$

$$\begin{array}{rcl}f(n+1,k)& =& \sum _{i=1}^{n+1}{i}^k\cdot m^i\\ & =& m+\sum _{i=2}^{n+1}{i}^k\cdot m^i\\ & =& m+m\sum _{i=1}^n(i+1{)}^k\cdot m^i\\ & =& m+m\sum _{i=1}^n\sum _{j=0}^k{C}_k^j\cdot i^j\cdot m^i\\ & =& m+m\sum _{j=0}^k{C}_k^j\cdot \sum _{i=1}^n{i}^j\cdot m^i\\ & =& m+m\sum _{j=0}^k{C}_k^j\cdot f(n,j)\end{array}$$

$$\begin{array}{rcl}f(2n,k)& =& \sum _{i=1}^{2n}{i}^k\cdot m^i\\ & =& \sum _{i=1}^n{i}^k\cdot m^i+\sum _{i=n+1}^{2n}{i}^k\cdot m^i\\ & =& f(n,k)+\sum _{i=1}^n(i+n{)}^k\cdot m^{i+n}\\ & =& f(n,k)+m^n\sum _{i=1}^n{m}^i\cdot \sum _{j=0}^k{C}_k^j\cdot i^j\cdot n^{k-j}\\ & =& f(n,k)+m^n\sum _{j=0}^k{C}_k^j\cdot n^{k-j}\cdot \sum _{i=1}^n{i}^j\cdot m^i\\ & =& f(n,k)+m^n\sum _{j=0}^k{C}_k^j\cdot n^{k-j}\cdot f(n,j)\end{array}$$

所以我们只要花$O(m^2)$的时间就能从$n$转移到$n+1$或者$2n$，类似快速幂的思想就能在$O(m^{2}log(n))$的时间内解决这题。

Sol-2 $O(m^2)$

好像网络上的题解都是这个复杂度。

令 $f(k)=\sum _{i=1}^n{i}^k\cdot m^i$

$$\begin{array}{rcl}(m-1)\cdot f(k)& =& \sum _{i=1}^n{i}^k\cdot m^{i+1}-\sum _{i=1}^n{i}^k\cdot m^i\\ & =& \sum _{i=2}^{n+1}(i-1{)}^k\cdot m^i-\sum _{i=1}^n{i}^k\cdot m^i\\ & =& n^k\cdot m^{n+1}+\sum _{i=1}^n{m}^i\cdot [(i-1{)}^k-i^k]\\ & =& n^k\cdot m^{n+1}+\sum _{i=1}^n{m}^i\cdot \sum _{j=0}^{k-1}{C}_k^j\cdot i^j\cdot (-1{)}^{k-j}\\ & =& n^k\cdot m^{n+1}+\sum _{j=0}^{k-1}{C}_k^j\cdot (-1{)}^{k-j}\cdot \sum _{i=1}^n{i}^j\cdot m^i\\ & =& n^k\cdot m^{n+1}+\sum _{j=0}^{k-1}{C}_k^j\cdot (-1{)}^{k-j}\cdot f(j)\\ f(k)& =& \frac{n^k\cdot m^{n+1}+\sum _{j=0}^{k-1}{C}_k^j\cdot (-1{)}^{k-j}\cdot f(j)}{m-1}\end{array}$$ 特判$m=1$的情况，当$m\ne 1$时直接用上面的式子$O(m^2)$转移。

Sol-3 $O(m)$

Orz完杜教的ppt才懂

令$G(n)=\sum _{i=0}^{n-1}{i}^m\cdot m^i$，注意这里只加到$n-1$

然后把$m$很小的时候的公式找出来：

$$\begin{array}{rcl}m=2& G(n)=& 2^n\cdot (n^2-4\cdot n+6)-6\\ m=3& G(n)=& 3^n\cdot (\frac{4\cdot n^3-18\cdot n^2+36\cdot n-33}{8})+\frac{33}{8}\\ m=4& G(n)=& 4^n\cdot (\frac{27\cdot n^4-144\cdot n^3+360\cdot n^2-528\cdot n+380}{81})-\frac{380}{81}\\ m=5& G(n)=& 5^n\cdot (\frac{128\cdot n^5-800\cdot n^4+2400\cdot n^3-4600\cdot n^2+5700\cdot n-3535}{512})+\frac{3535}{512}\\ m=6& G(n)=& 6^n\cdot (\frac{3125\cdot n^6-22500\cdot n^5+78750\cdot n^4-183000\cdot n^3+305550\cdot n^2-340020\cdot n+189714}{10625})-\frac{189714}{15625}\end{array}$$

//公式最后一项的有理数还是一个神奇的数列

根据上面这些公式，不难得出答案的式子一定是长这样的：

$$G(n)=m^n\cdot F_m(n)-F_m(0)$$

其中$F_m(n)$是一个m次多项式(代入$n$后的值)，形如$c_0\cdot n^m+c_1\cdot n^{m-1}+...+c_{m-1}\cdot n+c_m$

归纳法证一下发现结论是对的。

所以

$$G(n+1)-G(n)=n^m\cdot m^n=m^{n+1}\cdot F_m(n+1)-m^n\cdot F_m(n)$$ $$n^m=m\cdot F_m(n+1)-F_m(n)$$ $$F_m(n+1)=\frac{n^m+F_m(n)}{m}$$

设$F_m(0)=x$，则$F_m(1)$~$F_m(m+1)$都能通过上面的递推式变成形如$Ax+B$的形式。

由于$F_m(n)$是一个次数为$m$的多项式(代入$n$后的值)，所以有下面这个式子：

$$\sum _{i=0}^{m+1}(-1{)}^i\cdot C_{m+1}^i{F}_m(i)=0$$

为什么呢？

首先，$F_m(i)$是可以线性表示成若干个组合数之和，于是我们只要证明

$$\mathrm{\forall }k\le m,\sum _{i=0}^{m+1}(-1{)}^i\cdot C_{m+1}^i{C}_i^k=0$$

注意到$i$的范围只能是$[k,m+1]$，否则后面那坨东西直接变成0。

$$\begin{array}{rcl}& & \sum _{i=k}^{m+1}(-1{)}^i\cdot C_{m+1}^i\cdot C_i^k\\ & =& \sum _{i=k}^{m+1}(-1{)}^i\cdot \frac{(m+1)!}{i!\cdot (m+1-i)!}\cdot \frac{i!}{k!\cdot (i-k)!}\\ & =& \frac{(m+1)!}{(m+1-k)!\cdot k!}\sum _{i=k}^{m+1}(-1{)}^i\cdot \frac{(m+1-k)!}{(m+1-i)!\cdot (i-k)!}\\ & =& C_{m+1}^k\sum _{i=k}^{m+1}(-1{)}^i\cdot C_{m+1-k}^{i-k}\\ & =& C_{m+1}^k\sum _{i=0}^{m+1-k}(-1{)}^{i-k}\cdot C_{m+1-k}^i\\ & =& (-1{)}^k\cdot C_{m+1}^k\cdot (1-1{)}^{m+1-k}=0\end{array}$$

于是这个鬼畜的结论就证完啦~对任意$m$次多项式都能用~

然后就能根据这个式子列方程，就能把$F_m(0)$给解出来。

然而题目不是叫你求$F_m(0)$，而是求$m^n\cdot F_m(n)-F_m(0)$

当$n\le m$的时候，好办，把之前用到的$F_m(n)=A(n)\cdot F_m(0)+B(n)$直接算一下，然后就能得到答案了。

当$n>m$的时候，？

假设我们已经求出了$F_m(0),F_m(1),...,F_m(m)$

令$$F_m(n)=\sum _{k=0}^m{C}_n^k{a}_k$$

经过二项式反演可得$$a_k=\sum _{j=0}^k(-1{)}^{k-j}\cdot C_k^j\cdot F_m(j)$$

$$\begin{array}{rcl}{F}_m(n)& =& \sum _{k=0}^m{C}_n^k\sum _{j=0}^k(-1{)}^{k-j}\cdot C_k^j\cdot F_m(j)\\ & =& \sum _{j=0}^m{F}_m(j)\cdot \sum _{k=j}^m(-1{)}^{k-j}\cdot C_n^k\cdot C_k^j\\ & =& \sum _{j=0}^m{F}_m(j)\cdot \sum _{k=j}^m(-1{)}^{k-j}\cdot \frac{n!\cdot k!}{k!\cdot (n-k)!\cdot j!\cdot (k-j)!}\\ & =& \sum _{j=0}^m{F}_m(j)\cdot \sum _{k=j}^m(-1{)}^{k-j}\cdot \frac{n!\cdot (n-j)!}{(n-k)!\cdot j!\cdot (k-j)!\cdot (n-j)!}\\ & =& \sum _{j=0}^m{F}_m(j)\cdot \sum _{k=j}^m(-1{)}^{k-j}\cdot C_n^j\cdot C_{n-j}^{k-j}\\ & =& \sum _{j=0}^m{F}_m(j)\cdot C_n^j\cdot \sum _{k=0}^{m-j}(-1{)}^k\cdot C_{n-j}^k\\ & =& \sum _{j=0}^m{F}_m(j)\cdot C_n^j\cdot (-1{)}^{m-j}\cdot C_{n-j-1}^{m-j}\\ & =& \sum _{j=0}^m{F}_m(j)\cdot (-1{)}^{m-j}\cdot \frac{n!\cdot (n-j-1)!}{j!\cdot (n-j)!\cdot (m-j)!\cdot (n-m-1)!}\\ & =& \frac{n!}{(n-m-1)!}\sum _{j=0}^m{F}_m(j)\cdot (-1{)}^{m-j}\cdot \frac{1}{j!\cdot (m-j)!\cdot (n-j)}\\ & =& \sum _{j=0}^m{F}_m(j)\cdot (-1{)}^{m-j}\cdot \frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{j!\cdot (m-j)!\cdot (n-j)}\end{array}$$

$\frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{n-j}$可以用一个前缀乘积和一个后缀乘积优化成$O(m)$的预处理复杂度。

所以只要花$O(m)$的时间就好了。

上面有一步用到了这个式子(第六行到第七行)： $$\begin{array}{rcl}\sum _{i=0}^k(-1{)}^i\cdot C_n^i& =& C_n^0-C_n^1+...\\ & =& C_{n-1}^0-C_n^1+...\\ & =& -C_{n-1}^1+C_n^2-...\\ & =& C_{n-1}^2-C_n^3+...\\ & =& (-1{)}^k\cdot C_{n-1}^k\end{array}$$

复杂度分析：求$1$~$m+1$的所有阶乘、逆元、阶乘逆元以及$i^m$都能做到$O(m)$的时间复杂度。

求$\mathrm{\forall }i\in [1,m]F_m(i)$也只要用线性复杂度。

当$n\le m$的时候，只要用$O(1)$的时间得到答案。

当$n>m$的时候，照着最后一个式子求。前面的乘数花$O(m)$的时间算，后面的$\frac{n\cdot (n-1)\cdot ...\cdot (n-m)}{n-j}$,$\frac{1}{j!}$和$\frac{1}{(m-j)!}$直接$O(1)$

打了一个下午题解终于把这个坑给填了233

其实我已经在这篇blog里面贴了代码，然而只有神犇才能看得见。