请选择 进入手机版 | 继续访问电脑版

【训练题25:数学+位运算】E : Apollo versus Pan | CF Good Bye 2020

[复制链接]
期待幸福 发表于 2021-1-2 19:44:35 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
E : Apollo versus Pan | CF Good Bye 2020
题外话

有大概是太晚了太困了,大概是按位运算的数学太差了///
做了好久都没有起色,于是草草睡觉了
第二天补一下题
难度

                               −                               3370                         14603                                  -\frac{3370}{14603}               −146033370​
题意

给你一个长度为                               n                          n               n 的序列                                        x                         n                                  x_n               xn​
让你求
                                              ∑                                       i                               =                               1                                      n                                            ∑                                       j                               =                               1                                      n                                            ∑                                       k                               =                               1                                      n                                  (                                   x                            i                                  &                                   x                            j                                  )                         ×                         (                                   x                            j                                  ∣                                   x                            k                                  )                               \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n(x_i\&x_j)\times(x_j|x_k)                   i=1∑n​j=1∑n​k=1∑n​(xi​&xj​)×(xj​∣xk​)
答案取模                               1                      e                      9                      +                      7                          1e9+7               1e9+7
此中                               &                          \&               & 是按位与运算 ,                               ∣                          |               ∣ 是 按位或运算
数据范围

                               0                      ≤                               x                         i                              ≤                               2                         60                                  0\le x_i\le 2^{60}               0≤xi​≤260
                               1                      ≤                      n                      ≤                      5                      ×                      1                               0                         5                                  1\le n\le 5\times10^5               1≤n≤5×105
思路

  求                                    F                         (                         i                         )                              F(i)                  F(i)



  • 容易想到,应该按位思量
  • 对于二进制右数第                                   c                              c                  c位(base为0),只有两个数的这一位都为                                    1                              1                  1,才会对答案贡献                                              2                            c                                       2^c                  2c
  • 那我们盘算                                    F                         (                         i                         )                              F(i)                  F(i) , 首先要求                                                    x                               i                                            x_i                     xi​ 的这一位必须是                                         1                                  1                     1,接下来其他数有多少个数这一位是                                         1                                  1                     1,就对答案贡献频频
  • 设                                    c                         n                                   t                            c                                       cnt_c                  cntc​ 体现有多少个数字二进制右数第                                   c                              c                  c位为                                    1                              1                  1。
  • 设                                              w                            c                                  (                                   x                            i                                  )                              w_c(x_i)                  wc​(xi​)体现数字                                              x                            i                                       x_i                  xi​的二进制右数第                                   c                              c                  c位的值(为                                    0                              0                  0 或为                                    1                              1                  1 )
  •                                    F                         (                         i                         )                         =                                   ∑                                       c                               =                               0                                      ∞                                            2                            c                                  ×                                   w                            c                                  (                                   x                            i                                  )                         ×                         c                         n                                   t                            c                                       F(i)=\sum_{c=0}^{\infin} 2^c\times w_c(x_i)\times cnt_c                  F(i)=∑c=0∞​2c×wc​(xi​)×cntc​ ,答案=每次贡献代价*贡献次数。
求                                    G                         (                         i                         )                              G(i)                  G(i)

  个人总结

一个多值变量                                    x                              x                  x 如果能取值到                                   {                                   v                            1                                  ,                         ⋯                          ,                                   v                            n                                  }                              \{v_1,\cdots,v_n\}                  {v1​,⋯,vn​} 的时候的一些表达式盘算:

  • 只有当                                    x                              x                  x 取值                                              v                            i                                       v_i                  vi​时,对答案贡献                                    k                              k                  k,否则贡献为                                    0                              0                  0 的表达式:
                                        a                         n                         s                         =                         χ                         [                         (                         x                         −                                   v                            1                                  )                         (                         x                         −                                   v                            2                                  )                         ⋯                         (                         x                         −                                   v                                       k                               −                               1                                            )                         (                         x                         −                                   v                                       k                               +                               1                                            )                         ⋯                         (                         x                         −                                   v                            n                                  )                         ≠                         0                         ]                         ×                         k                              ans=\chi \Big[(x-v_1)(x-v_2)\cdots(x-v_{k-1})(x-v_{k+1})\cdots(x-v_n)\ne0\Big]\times k                  ans=χ[(x−v1​)(x−v2​)⋯(x−vk−1​)(x−vk+1​)⋯(x−vn​)​=0]×k
  • (1.的拓展)只有当                                    x                              x                  x 取值为聚集                                   S                         =                         {                                   v                            i                                  }                              S=\{v_i\}                  S={vi​}中的聚集对答案贡献                                    k                              k                  k,否则无贡献的表达式:
                                        a                         n                         s                         =                         k                         ×                         χ                         [                                   ∏                            i                                  (                         x                         −                                   v                            i                                  )                         ≠                         0                         ]                              ans=k\times\chi \Big[\prod_i(x-v_i)\ne0\Big]                  ans=k×χ[∏i​(x−vi​)​=0],此中                                              v                            i                                  ∉                         {                         S                         }                              v_i\notin\{S\}                  vi​∈/​{S}
  • (                                   n                              n                  n个多值变量拓展)只有当                                              x                            1                                  ≠                                   v                            1                                  ,                         ⋯                                   x                            j                                  ≠                                   v                            j                                       x_1\ne v_1,\cdots x_j\ne v_j                  x1​​=v1​,⋯xj​​=vj​ 同时满足时对答案贡献                                    k                              k                  k,否则无贡献的表达式:
                                        a                         n                         s                         =                         k                         ×                         χ                         [                                   ∏                            i                                  (                                   x                            i                                  −                                   v                            i                                  )                         ≠                         0                         ]                              ans=k\times\chi \Big[\prod_i(x_i-v_i)\ne0\Big]                  ans=k×χ[∏i​(xi​−vi​)​=0]
    此中                                    χ                         [                         F                         ]                              \chi\Big[F\Big]                  χ[F] 为艾弗森括号,体现若                                    F                              F                  F为真则值为                                    1                              1                  1,否则值为                                    0                              0                  0。
                                    n                              n                  n 个双值变量                                              x                            i                                       x_i                  xi​ 只取                                   {                         0                         ,                         1                         }                              \{0,1\}                  {0,1} 的时候的一些表达式盘算:

  • 全取                                    1                              1                  1 才有贡献                                    k                              k                  k
                                        a                         n                         s                         =                         k                         ×                                   ∏                            i                                            x                            i                                       ans=k\times\prod_ix_i                  ans=k×∏i​xi​
  • 全取                                    0                              0                  0 才有贡献                                    k                              k                  k
                                        a                         n                         s                         =                         k                         ×                                   ∏                            i                                  (                         1                         −                                   x                            i                                  )                              ans=k\times \prod_i(1-x_i)                  ans=k×∏i​(1−xi​)
  • 至少有一个变量取                                    0                              0                  0 就对答案有贡献                                    k                              k                  k (大概要么                                             x                            1                                       x_1                  x1​取                                   0                         ⋯                              0\cdots                  0⋯要么                                             x                            n                                       x_n                  xn​取                                   0                              0                  0就有贡献                                    k                              k                  k)
                                        a                         n                         s                         =                         k                         ×                         (                         1                         −                                   ∏                            i                                            x                            i                                  )                              ans=k\times(1-\prod_i x_i)                  ans=k×(1−∏i​xi​)
  • 至少有一个变量取                                    1                              1                  1 就对答案有贡献                                    k                              k                  k (大概要么                                             x                            1                                       x_1                  x1​取                                   1                         ⋯                              1\cdots                  1⋯要么                                             x                            n                                       x_n                  xn​取                                   1                              1                  1就有贡献                                    k                              k                  k)
                                        a                         n                         s                         =                         k                         ×                         (                         1                         −                                   ∏                            i                                  (                         1                         −                                   x                            i                                  )                         )                              ans=k\times(1-\prod_i (1-x_i))                  ans=k×(1−∏i​(1−xi​))
其他的一些细节

<ul>只要预处理处罚好                                    c                         n                                   t                            i                                       cnt_i                  cnti​ 就可以了,其他内容都可以很简朴盘算得到。
因为                                              x                            i                                       x_i                  xi​最多取值到                                              2                            60                                       2^{60}                  260,因此式子中的                                    c                         ∈                         {                         0                         ,                         1                         ,                         ⋯                          ,                         60                         }                              c\in\{0,1,\cdots,60\}                  c∈{0,1,⋯,60},复杂度并不高
取第                                   c                              c                  c位的代码应该写成(1LL
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )