卡了三天常数总算卡过去了。
https://loj.ac/submission/201339
顺带吐槽一下某谷。
原题5s时限，512M内存限制，到了你谷怎么成2s 128M了。
还让不让人做题了。
不知道为什么自己常数这么大…
也不知道为什么自己不用long double就会有精度问题…
$$ \text{设}F\left( x \right) \text{中}i\text{次项前的系数为将}i\text{表示为}S\text{中元素之和的方案数，}a_i\text{是}S\text{中是否存在元素}i \\ F\left( x \right) =\prod_{1\le i<p}{\left( \frac{1}{1-x^i} \right) ^{ai}} \\ \text{两边取对数} \\ \ln\text{\ }F\left( x \right) =-\sum_{1\le i<p}{a_{i\}\ln \left( 1-x^i \right)} \\ \text{对}\ln \left( 1-x^i \right) \text{在}x=\text{0处泰勒展开} \\ \text{把}\ln \left( 1-x^i \right) \text{对}x^i\text{求导} \\ g\left( x \right) =\ln \left( 1-x^i \right) \\ g`\left( x \right) =\left( x^i-1 \right) ^{-1} \\ g“\left( x \right) =-1\left( x^i-1 \right) ^{-2} \\ g“`\left( x \right) =2\left( x^i-1 \right) ^{-3} \\ g^{\left( n \right)}\left( x^i \right) =\left( -1 \right) ^{n-1}\left( n-1 \right) !\left( x^i-1 \right) ^{-n} \\ \text{令}x^i=0 \\ g^{\left( n \right)}\left( 0 \right) =-\left( n-1 \right) ! \\ \ln\text{\ }F\left( x \right) =\sum_{1\le i<p}{a_i\sum_{j\ge 1}{\frac{x^{ij}}{j}}} \\ \ln\text{\ }F\left( x \right) =\sum_{1\le T\le n}{x^T\times \frac{1}{T}\sum_{i|T}{a_i\times i}} \\ \text{设}f\left( T \right) =\frac{1}{T}\sum_{i|T}{a_i\times i} \\ \ln\text{\ }F\left( x \right) =\sum_{1\le T\le n}{x^Tf\left( T \right)} \\ \text{设}g\left( i \right) =a_i\times i \\ Tf\left( T \right) =\left( g*1 \right) \left( T \right) \\ g\left( T \right) =\sum_{i|T}{\mu \left( \frac{T}{i} \right) if\left( i \right)} \\ a_T=\frac{1}{T}\sum_{i|T}{\mu \left( \frac{T}{i} \right) if\left( i \right)} \\ \text{因为已知所有的}f\left( i \right) ,\text{所以可以求出所有的}a_i \\ \\ \\ \\ \\ \\ $$
发表回复