注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

CTSC 2014 闲扯  

2014-05-22 00:10:16|  分类: CTSC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
呼啦啦搞完了……
由于准备湖北省队互测Week1的缘故到现在才全部A掉 >_<....(图像识别那题咱们另算……非传统题我实在A不掉……)

不准备写详细题解了……官方题解其实已经非常详细了……

企鹅QQ
直接hash就行了囧……

插线板

随机数
无限orz clj。
我分了3种情况:
type = 0, m <= 2000, k <= 10^9:
    暴力压位多项式快速幂。
type = 0, m <= 1000000, k <= 10^6:
    用FFT优化多项式除法。值得一提的是原本的公式是递推每次执行r(x) = (2r(x) - f(x) * r(x) * r(x)) % x^(2n)
    但是由于是模2意义下,所以直接就是r(x) = (f(x) * r(x) * r(x)) % x^(2n)。(感觉像是某种快速幂?吓傻了)
type = 1, m <= 1000
    暴力压位快速幂求多项式的逆元。由题目条件知非零元素带上乘法形成了一个循环群,未定元x是这个群的生成元。由于是群,由拉格朗日子群定理知,每个元素的(2^m - 1)次方为单位元1。所以个元素的(2^m - 2)次方是这个元素的逆。
    这样的话已知g(x) = f(x) * x^(k * 2^l) (mod (x^m + m(x)))
    则x^(k * 2^l) = g(x) * f^(-1)(x) (mod (x^m + m(x)))
    则x^(k * 2^l)^(2^(m - l)) = (g(x) * f^(-1)(x))^(2^(m - l)) (mod (x^m + m(x)))
    则x^k = (g(x) * f^(-1)(x))^(2^(m - l)) (mod (x^m + m(x)))
    则f(x) x^k = f(x) (g(x) * f^(-1)(x))^(2^(m - l)) (mod (x^m + m(x)))
    (排版好糟糕 T_T.....)

小秘密
无限orz fhq。一道非常非常有意思的神题。
首先这个问题可以化为解带噪声的模2意义下的线性方程组。
我们分三歩:求0~19位,求20~39位,求40~59位。
就以求0~19位为例吧。
把所有方程的20~39位所对应的值相同的加起来,这样就得到了7M个与20~39无关的线性方程组。
然后再把这些方程的40~59位所对应的值相同的加起来,这样就得到了6M个只与0~19有关的线性方程组。
然后暴力带入2^20个解验证是否合法。找满足的方程和不满足的方程的个数之差最大的即可。
于是现在就是要对每个解求:满足的方程 - 不满足的方程的个数
设方程分别为A_i * x = b_i,就是求:
        -------                        -------
         \          [A_i * x != b_i]    \          A_i * x + b_i
f(x) =    |     (-1)                 =   |     (-1)
         /                              /
        -------                        -------
           i                               i

                    19                        
        ------- -----------
         \        |     |       A_i_j * x_j       b_i
      =   |       |     |   (-1)             (-1)
         /        |     |
        -------   |     |
           i       k = 0
于是我们重新设:
                    19                        
        ------- -----------
         \        |     |       A_i_j      b_i
F(x)  =   |       |     |   x_j        (-1)
         /        |     |
        -------   |     |
           i       k = 0
易知F是个20元多项式,我们要把每一维分别带入-1和1,算出对应的F(x),就能知道把x的-1看成1,1看成0后形成的向量y的f(y)值。
用高维FFT即可解决问题 = =……
虽然很值得吐槽但是不得不说确实是高维FFT,因为-1和1确实是二次单位根,所以其实是要求DFT。
其实意思就是说,假设未知数分别是x1, ..., x_n:
f( 1, x_2, ..., x_n) = fa(x_2, ..., x_n) + fb(x_2, ..., x_n)
f(-1, x_2, ..., x_n) = fa(x_2, ..., x_n) - fb(x_2, ..., x_n)
所以问题变成了求fa和fb的DFT。这样递归下去,然后再合并就可以做到O(2^n)
http://fayaa.com/code/view/28120/

图的分割
排个序然后能不边就不缩边。跪傻了。
ym 当场AC的神犇。
  评论这张
 
阅读(1976)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017