Main » 2013 December 17 » [Sdoi2008]沙拉公主的困惑
4:42 PM [Sdoi2008]沙拉公主的困惑 |
这题溢了一次内存，然后就A了，好开心这道题容斥对于有经验的OIer应该能看出来，关键是不能每次都容斥，要巧妙地计算一些东西，这个我想了20min设p[i]=第i个质数 T[i]=前i个的质数的乘积,定义F[i]=(-1)^(i+1) ∑p[x1](x1∈[1,i])+(-1)^(i+2) ∑p[x1]*p[x2] (x1,x2∈[1,i] x1!=x2)(-1)^(i+3) ∑p[x1]*p[x2]*p[x3](x1,x2,x3∈[1,i] x1!=x2 x1!=x3 x2!=x3) …… F[n]的关键递推式:F[n]=F[n-1]*p[n]+T[i-1]-F[i-1] 为什么？算一下就知道了那么ans=fac[n]-(fac[n]*F[P]/T[P])关于/T[P]求个逆元吧Code:b2186 |
|
|
| Total comments: 0 | |