Google Code Jam Round1A "Number"

by 小伟

Google Code Jam Round1A "Number"

题目描述：给定一个数n（2 <= n <= 2000000000），求$$(3+\sqrt{5})^n的整数部分最后三位。

For example, when n = 5, $$(3+\sqrt{5})^5 = 3935.73982... $$ The answer is 935.

解法：

1. 直接求，要求精度高，当n>28时，结果就出错。

2. 技巧解法，配数法：

首先设

$$F(X)=\lfloor(3+\sqrt{5})^x\rfloor$$

$$G(X)=(3+\sqrt{5})^x+(3-\sqrt{5})^x$$

把G(X)展开，得到：

$$G(X)=\sum_{i=0}^{x}(3)^{x-i}(\sqrt{5})^i+\sum_{i=0}^{x}(3)^{x-i}(\sqrt{5})^i(-1)^i$$ 

展开后发现，包含$$\sqrt{5}$$ 的项都相互抵消了，得到：

 $$G(X)=\sum_{i=0}^{x/2}3^{(x-2*i)}5^{i}$$

从上式中可以看出，G(X)是整数。

由于$$0<(3-\sqrt{5})^x\leq1，因此$$F(X)=G(X)-1$$。

于是问题就转化为求G(X)，求G(X)也是使用配数法，如下：

6\times G(X)=G(X)\times(3+\sqrt{5})+G(X)\time(3-\sqrt{5})$$

=\lbrack(3+\sqrt{5})^x+(3-\sqrt{5})^x\rbrack\times(3+\sqrt{5})+\lbrack(3+\sqrt{5})^x+(3-\sqrt{5})^x\rbrack\times(3-\sqrt{5})$$

=\lbrack(3+\sqrt{5})^{x+1}+(3-\sqrt{5})^{x+1}\rbrack+4\times\lbrack(3+\sqrt{5})^{x-1}+(3-\sqrt{5})^{x-1}\rbrack

=G(x+1)+4\times G(x-1)

因此，得到递推公式G(x+1)=6\times G(x)-4\times G(x-1)

由于题目中的n值较大，不能直接使用递推公式，我们可以构造一个矩阵来加速求解：

$$\begin{bmatrix}G(x+1)\\G(x)\end{bmatrix}=\begin{bmatrix}6 & -4\\1 & 0\end{bmatrix}\begin{bmatrix}G(x)\\G(x-1)\end{bmatrix}

其中$$G(1)=6, \;G(2)=28，所以

$$\begin{bmatrix}G(x+1)\\G(x)\end{bmatrix}=\begin{bmatrix}6 & -4\\1 & 0\end{bmatrix}^{x-1}\begin{bmatrix}G(2)\\G(1)\end{bmatrix}

使用按位乘法，就可以在Log(x)的复杂度内，求出G(X)。

至此，本题顺利解决。


Problem Analysis Google Code Jam 配数法 递推公式 矩阵加速 Comments(44) 2008年8月02日 14:29

World Final 2008 Problem B -- 判断多项式恒被整除

by F.Yang   

      ACM/ICPC World Final 2008 Problem B  给定整系数多项式 f(x) 及正整数d. 判断对x 取遍所有整数, f(x) 是否恒被d整除.

      分析  我们先定义一些概念.

      定义1  设f(x)为整系数多项式, d 为非零整数, 若对任意 x \in Z, 都有 d \mid f(x). 我们则称 f(x) 恒被 d 整除.

      定义2  记f^{(0)}(x) = f(x), \Delta  为向前差分算子, 定义n 阶差分多项式(简称n 阶差分)

f^{(n)}(x) = \Delta f^{(n-1)}(x) = f^{(n-1)}(x+1) - f^{(n-1)}(x) \,\,\,\,\,\,\, ( n>0 ).

      我们有如下定理.

      定理1  整系数多项式 f(x) 恒被d整除, 当且仅当f(0)被d 整除, 且f(x) 的一阶差分f^{(1)}(x)恒被d 整除.

      证明  充分性. 因为f(x) 恒被d整除, 所以 d \mid f(0), d \mid f(x+1) - f(x) = f^{(1)}(x) (x \in Z). 充分性得证.

      必要性. 使用数学归纳法. d \mid f(0). 设对非负整数数x, 都有d \mid f(x). 又因为d \mid f^{(1)}(x), 故d \mid f(x)+ f^{(1)}(x) = f(x+1). 同理, 设对整数x, 有d \mid f(x). 则d \mid f(x) - f^{(1)}(x-1) = f(x-1). 综合上述, 由数学归纳法知, 必要性得证.  \Box

      定理2  设整系数多项式f(x)的次数为m= \partial (f(x)), 则f(x)恒被非零整数d整除, 当且仅当 f(0), f(1), \cdots , f(m)均被d整除. 

      证明  充分性是显然的.

      必要性的证明施归于纳多项式的次数m. 当m=0, 即f(x)为常数时, 结论显然成立. 设m \leq k时结论成立. 则对m=k+1次多项式f(x), 若f(0), f(1), \cdots , f(k), f(k+1)均被d 整除, 则f^{(1)}(0)=f(1)-f(0), f^{(1)}(1)=f(2)-f(1), ... , f^{(1)}(k)=f(k+1)-f(k) 均能被d整除。又有\partial(f^{(1)}(x))<\partial(f(x))=k+1. 由归纳假设知, 一阶差分f^{(1)}(x) 恒被d 整除. 又根据定理1, 得知f(x) 恒被d 整除. 由数学归纳法, 必要性得证.   \Box

      定理3  设整系数多项式f(x)的次数为m= \partial (f(x)), 则f(x)恒被非零整数d整除, 当且仅当对任意连续m+1个整数x_0, x_0+1, \cdots, x_0+m, 有f(x_0), f(x_0+1), \cdots, f(x_0+m)均被d整除.

      定理3作为定理2的推广, 证明方法也是类似的, 此处从略.

      推论1  设整系数多项式f(x)的次数为m= \partial (f(x)), g=(f(0), f(1), \cdots, f(m)), f(x)恒被d整除当且仅当d \mid g.

      至此，整个问题得到完整解决.   

Problem Analysis 多项式 整除 差分 Comments(10) 2008年7月27日 04:34

CII2187-一般任务安排问题的最小费用最大流解法及其他

by F.Yang     

      CII-2187问题描述：一人以看录像维生.  每个录像有三个属性 (s, f, p) 分别表示该任务的开始时间，结束时间和所得收入. 但这个人在同一时刻最多只能看两个录像. 现给定 n 个录像. 问这个人的最大收入是多少.

      分析： 我们把问题一般化, 设这个人在同一时刻最多能看 k 个电影. 我们使用最小费用最大流来解决这个问题.

      把每个任务的开始时间和结束时间都对应设为图的一个顶点. 对每个任务 (s, f, p), s 结点到 f 结点连一条弧, 容量为1, 费用为 -p. 而对任意两个任务(si, fi, pi), (sj, fj, pj), 如果fi<=sj, 则从 fi 到 sj 连一条弧, 容量为1, 费用为0. 设一超级源 R0, R0 到各个任务的开始时间 si 都连一条容量为1, 费用为0的弧. 再设一超超级源 R1, R1仅有到R0容量为k, 费用为0的弧. 最后设一超级汇 R2, 各任务的结束时间 fi 到R2都有一条容量为1, 费用为0的弧.

      求从 R1 到 R2 的最小费用最大流, 得到费用 cost, 则 -cost 即为问题的答案.

      讨论： 虽然上述算法在一般化的角度解决了这个问题, 但是由于解决费用流的算法复杂度约为O(N^3), 这在某些有特殊限制的问题变种里并不见得是一种首选的高效算法. 现在总结一下一些特殊的变种及适合的方法.

      (1) 单资源无费用. 如果上题那个人任一时刻只能看一个录像, 并且每看一个录像的收入都是1, 那么这是一个经典的活动安排问题. 任务按结束时间排序后使用贪心算法即可解决. 算法的时间复杂度为O(NlogN)+O(N)=O(NlogN).

      (2) 单资源有费用. 如果上题观看者每一时刻都只能看一个录像. 任务按结束时间排序后使用一个DP即可, 设 dp[i] 表示以任务 i 结束的情况下所能获得的最大收益. 该算法的时间复杂度为O(NlogN)+O(N^2)=O(N^2).

      (3) 多资源无费用. 如果上题里观看者每一时刻最多可以看k个录像, 但是看每个录像的收入都是1. 可以使用如下算法解决:
      a. 维护一个数据结构T, 表示各个资源的最后可用时间, 初始时里面有k个0;
      b. 将任务按结束时间排序; 
      c. 顺序扫描每个任务 (s, f), 在 T 里面查找一个不大于 s 的最大的元素 t. 如果能找到, 则选取该任务, 并将 t 更新为 f 加入回 T 中, 若不能找到 t, 则放弃该任务.
      T使用平衡树来维护, 每次查找和更新的复杂度为O(logK), 整个算法的复杂度为O(NlogN)+O(NlogK)=O(N(logN+logK)). 但编码的复杂度很大.

      (4) 两资源有费用. 这即为原题本身. 可以使用两维状态的三方dp来解决. 小伟已经使用该方法通过了该题. 呼唤小伟给出算法详解和代码.

Problem Analysis 任务安排问题 最小费用最大流 Comments(11) 2008年7月22日 05:14

PKU1031-求点对多边形所成张角

by F. Yang     

    PKU1031题意描述：在坐标原点处有一个点光源S. 在距离S为r处的亮度为

I = k/r,

其中k为与光源有关的常数. 而光对在某处一高度为h长度为dl的小量竖直矩形的照度为

 dI = Ih \mid \cos \alpha \mid dl，

其中I为该小量矩形处的亮度，\alpha为光源到dl处的方向与dl的法线方向的夹角.

    现有一高度为 h的简单多边形篱笆，用点列P_0 \dots P_{n-1}描述. 原点不在多边形的边上. 求光源对多边形各处的照度的总和.

     分析： 设dl的两端点为A, B. 且A, B在光源S到直线AB的垂足的同侧, 否则只需要将AB从垂足处分为两条线段讨论即可. 另外假设A离垂足较近. 设S到AB的垂线与SA的夹角为\theta, 而S到AB的小量张角为d\theta. SA的长度为r. 由小量分析的方法可得

 dl = rd\theta/\cos\theta.

    易知\theta即为上述的\alpha. 故得到在dl处的照度为

 dI = h \cdot\frac{k}{r}\cdot\cos\theta\cdot\frac{rd\theta}{\cos\theta} = hkd\theta.

    显然，照度与距离无关，只与张角有关. 故这个问题变成求一个点对一个简单多边形的张角.

     求点对多边形张角的问题可以用投影和区间并的思想解决：

(1) 令P_n = P_0;

(2 )维护一个闭区间序列ints[], 初始为空;

(3) 对每条条线段P_iP_{i+1}, 0 \leq i < n, 求出向量\overrightarrow{SP_i}和\overrightarrow{SP_{i+1}}的辐角\alpha, \beta, 设\alpha \leq \beta. 若\beta - \alpha < \pi, 则将区间[\alpha, \beta]加入到序列ints[]中, 否则分别将区间[0, \alpha], [\beta, 2\pi]加入到序列ints[]中.

(4) 将区间序列ints[]按左端排序, 合并各个相交的区间;

(5) 最后剩下的不相交区间的长度总和就是所求夹角.

    下面为解决这个问题的代码, 函数接口为double angfun(pt p[], int n) , 由于本题光源刚好在原点，所以不当作参数, 对其他点也是容易处理的, 坐标平移一下即可.

  1. struct pt{
  2.         double x, y;
  3. };
  4.  
  5. struct interval{
  6.         double a, b;
  7. };
  8.  
  9. const double pi=acos(-1.0);
  10.  
  11. bool cmp(interval s1, interval s2)
  12. {
  13.         return s1.a<s2.a || s1.a==s2.a && s1.b<s2.b;
  14. }
  15.  
  16. double angle(pt p)
  17. {
  18.         double r, alpha;
  19.        
  20.         r=sqrt(p.x*p.x+p.y*p.y);
  21.         alpha=acos(p.x/r);
  22.         if(p.y<0) alpha=2*pi-alpha;
  23.         return alpha;
  24. }
  25.  
  26. double angfun(pt p[], int n)
  27. {
  28.         int i, m=0, t;
  29.         interval s[110];
  30.         double a, b, total;
  31.        
  32.         p[n]=p[0];
  33.        
  34.         for(i=0; i<n; i++){
  35.                 a=angle(p[i]);
  36.                 b=angle(p[i+1]);
  37.                 if(a>b) swap(a, b);
  38.                 if(b-a<pi-eps){
  39.                         s[m].a=a;
  40.                         s[m].b=b;
  41.                         m++;
  42.                 }
  43.                 else{
  44.                         s[m].a=0;
  45.                         s[m].b=a;
  46.                         m++;
  47.                         s[m].a=b;
  48.                         s[m].b=2*pi;
  49.                         m++;
  50.                 }
  51.         }
  52.        
  53.         sort(s, s+m, cmp);
  54.        
  55.         t=0;
  56.         for(i=1; i<m; i++)
  57.                 if(s[i].a<=s[t].b){
  58.                         if(s[t].b<s[i].b) s[t].b=s[i].b;
  59.                 }
  60.                 else s[++t]=s[i];
  61.                
  62.         total=0;
  63.         for(i=0; i<=t; i++) total+=s[i].b-s[i].a;
  64.        
  65.         return total;
  66. }
  67.  

    讨论： 假设允许点在多边形上, 这个方法也是可用的, 不过我们需要知道这个时候点是看作影响多边形外还是影响多边形内. 另外还需要判断每条边的左侧是内部还是右侧是内部. 这只要按叉积求一次面积即可判断. 具体在此从略. 本部分感谢bigheadghost提示.

    PS: PKU上该题做成多case会wrong到死, 要做成单case才能过, 晕死!

 

Problem Analysis 点对多边形张角 计算几何 Comments(15) 2008年7月22日 00:00




 

Host by is-Programmer.com | Power by Chito 1.3.3 beta
Designed by : Rambling Soul