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的原因，简直太神奇了！
题意 \(P=1e10+19\),求\(\sum x[i] mod P = 0\)的方案数，其中\(0 \leq x[i] < p - a[i]\)
做法