\(\color{green}{solution}\)

它每次感染的人是它的倍数,那么我们只需要找出那些除了自己以外在\(l\), \(r\)内没有别的数是

它的约数的数,在这里称其为关键数.

(比如区间是[3,7],那么这些数分别是\(3\),\(4\),\(5\),\(7\).因为\(6\)是\(3\)的倍数,所以不是).

我们记这些数的数量为\(sum\).那么设\(f_i\)为在第\(i\)时刻将说有人感染完的方案数.

那么换句话来说,就是最后一个关键数在第\(i\)时刻被感染.

那么\(f_i\) = \(sum\) \(\times (_{n-i}^{n-sum}) \times(i - 1)! \times(n-i)!\).所以最后\(ans = \sum_{i=sum}^{n} i \times f_i\)

BZOJ的垃圾评测机+卡常真的让人难受

#include 
    
     using namespace std;const int mod = 1e9 + 7, maxn = 1e7 + 10;int fac[maxn], ifac[maxn], l, r;int C(int n, int m) {     if( n < m) return 0;    return 1LL * fac[n] * ifac[m] % mod * ifac[n-m] % mod;}int _pow(int x, int n) {    int ret = 1;    for ( ; n; n >>= 1, x = 1LL * x * x % mod)         if( n & 1) ret = 1LL * ret * x % mod;    return ret;}bool book[maxn];int pri[maxn], ipri[maxn], cnt;int sum, ans, n;int main() {    scanf("%d%d", &l, &r);    fac[0] = 1;    for ( register int i = 1; i <= r; ++ i) {        fac[i] = 1LL * fac[i-1] * i % mod;    }    ifac[r] = _pow(fac[r], mod-2);    for ( register int i = r-1; ~i; -- i) {        ifac[i] = 1LL * ifac[i+1] * (i + 1) % mod;    }    if( l == 1) {        ans = 1LL * fac[r] * (r + 1) % mod * ifac[2] % mod;        printf("%d\n", ans); return 0;    }//  for ( register int i = l; i <= r; ++ i) if( !book[i]) {//      ++ sum;//      for ( register int k = i; k <= r; k += i) book[k] = 1;//  }    for ( register int i = 2; i <= r; ++ i) {        if( !book[i]) pri[++ cnt] = i, ipri[i] = 1;        for ( register int k = 1; k <= cnt; ++ k) {            if( 1LL * pri[k] * i > r) break;            ipri[i * pri[k]] = i; book[i*pri[k]] = 1;            if( i % pri[k] == 0) break;        }    }    for ( register int i = l; i <= r; ++ i) {        if( ipri[i] < l) ++ sum;    }    n = r - l + 1;    for ( register int i = sum; i <= n; ++ i) {        ans = (ans + 1LL * i * sum % mod * C(n - sum, n - i) % mod * fac[n - i] % mod * fac[i - 1] % mod) % mod;    }    printf("%d\n", ans);    return 0;}
    

吐槽:

九条可怜 + 组合数学 = 瞬间爆炸.还有为什么可以二次感染,度错题写了半天QAQ;

---