2019牛客国庆集训派对day5

时间:2021-03-12 14:55:27

2019牛客国庆集训派对day5


I.Strange Prime

题意 \(P=1e10+19\),求\(\sum x[i] mod P = 0\)的方案数,其中\(0 \leq x[i] < p - a[i]\)

做法

  • 神仙容斥,太妙啦
  • 首先考虑存在\(a[i] = 0\)时,其它数可任意选
  • 枚举哪些位置违反条件进行容斥
  • 列出式子发现,这简直就是二项式分解!
  • 但当所有位置都违反时,不存在可能的解,所以需要把它剪掉,这也就是数据小于1e5的原因,简直太神奇了!