題目鏈接

BZOJ5323

題解

有一些數(shù)是不能被別的數(shù)篩掉的
這些數(shù)出現(xiàn)最晚的位置就是該排列的\(t(p)\)
所以我們只需找出所有這些數(shù)，線性篩一下即可，設(shè)有\(m\)個(gè)
然后枚舉最后的位置
\[ans = \sum\limits_{i = m}^{n} m!(n - m)!{i - 1 \choose m - 1}i\]

復(fù)雜度\(O(n)\)

#include<iostream> #include<cstdio> using namespace std; const int maxn = 10000005,P = 1000000007; int p[maxn],isn[maxn],pi,L,R,len; int fac[maxn],fv[maxn],inv[maxn]; void pre(){fac[0] = fac[1] = inv[0] = inv[1] = fv[0] = fv[1] = 1;for (register int i = 2; i <= len; i++){fac[i] = 1ll * fac[i - 1] * i % P;inv[i] = 1ll * (P - P / i) * inv[P % i] % P;fv[i] = 1ll * fv[i - 1] * inv[i] % P;} } void init(){for (register int i = 2; i <= R; i++){if (!isn[i]) p[++pi] = i;for (register int j = 1; j <= pi && i * p[j] <= R; j++){isn[i * p[j]] = p[j];if (i % p[j] == 0) break;}} } int main(){scanf("%d%d",&L,&R); len = R - L + 1;pre();int cnt = 0;if (L == 1) cnt = 1;else{init();for (register int i = L; i <= R; i++){if (!isn[i] || i / isn[i] < L)cnt++;}}int ans = 0;for (register int i = cnt; i <= len; i++){ans = (ans + 1ll * fac[i - 1] % P * fv[i - cnt] % P * i % P) % P;}ans = 1ll * ans * cnt % P * fac[len - cnt] % P;printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9082269.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ5323 [Jxoi2018]游戏 【数论/数学】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。