题解 P4562 【[JXOI2018]游戏】

· · 题解

前言

因为本蒟蒻太菜了，看了题解才做出来这道题，感觉这道题难度适中，很适合练习推式子的能力，所以想到写一篇题解。同时感谢4526_这位大佬的题解，给了我很大的启发。

题意分析

编号为 x 的房间在被检查过之后，编号为 x 的倍数的房间就没有检查的必要了。因此，只要所有编号不是任何其他房间编号的倍数的房间被检查完，所有的房间一定都开始认真工作了。

题目可简化为：对于区间 l \sim n ，定义关键数为不被任何此区间其它数整除的数。求其所有排列最后一个关键数所在位置的总和。

做题思路

可以通过 O(n) 的时间复杂度（其实埃筛也可以过，但时间复杂度不对，我就用的埃筛）来搜索所有关键数，记其个数为 m 。

首先，根据期望的性质可知，期望 \times 总方案数 = 总和，所以我们可以先找出期望，在再其对应的方案数来求得总和。又因为期望等于概率 \times 贡献

所以答案可表示为 \sum_{i=m}^{n}(最后一个关键数在 i 位置的概率 \times i)\times 所有排列数

最后一个关键数在 i 的概率 = 最后一个关键数在 i 的方案数 / 总方案数 =\frac{\tbinom{m-1}{i-1}(n-m)!m!}{\tbinom{m}{n}(n-m)!m!}=\frac{\tbinom{m-1}{i-1}}{\tbinom{m}{n}}

ans=\sum_{i=m}^{n}(\frac{\tbinom{m-1}{i-1}}{\tbinom{m}{n}}\times i)\times n! =\sum_{i=m}^{n}(\frac{\frac{(i-1)!}{(m-1)!(i-m)!}}{\frac{n!}{m!(n-m)!}}\times i)\times n! =\sum_{i=m}^{n}(\frac{i!}{m!(i-m)!})\times m!\times m \times(n-m)! =\sum_{i=m}^{n}\tbinom{m}{i}\times m\times m!\times(n-m)!

易证：

\tbinom{m}{m}+\tbinom{m+1}{m} =\tbinom{m+1}{m+1} \tbinom{m}{m+1}+\tbinom{m+1}{m+1}=\tbinom{m+1}{m+2} \tbinom{m}{m+2}+\tbinom{m+1}{m+2}=\tbinom{m+1}{m+3} ...

故有：

\sum_{i=m}^{n}\tbinom{m}{i} =\tbinom{m}{m}+\tbinom{m}{m+1}+\tbinom{m}{m+2}+\tbinom{m}{m+3}+...+\tbinom{m}{n} =\tbinom{m}{m}+0+\tbinom{m}{m+1}+\tbinom{m}{m+2}+\tbinom{m}{m+3}+...+\tbinom{m}{n} \tbinom{m}{m}+\tbinom{m+1}{m}+\tbinom{m}{m+1}+\tbinom{m}{m+2}+\tbinom{m}{m+3}+...+\tbinom{m}{n} =\tbinom{m+1}{n+1}

带回原式，有：

ans=\tbinom{m+1}{n+1}\times m\times m!\times(n-m)! =\frac{(n+1)!}{(m+1)!(n-m)!}\times m\times m!\times(n-m) =\frac{m(n+1)!}{m+1}

Code

#include<bits/stdc++.h>
using namespace std;
int l,r;
bool b[10000001];
int n,m;
long long mod=1e9+7;
inline void find_key()
{
    for(register int i=l;i<=r;i++)
    {
        if(!b[i])
        {
            m++;
            for(register int j=2*i;j<=r;j+=i)
            {
                b[j]=1;
            }
        }
    }
    return ;
}
int main()
{
    cin>>l>>r;
    n=r-l+1;
    find_key();
    long long ans=m;
    for(register int i=2;i<=m;i++)
    {
        ans*=i;
        ans%=mod;
    }
    for(register int i=m+2;i<=n+1;i++)
    {
        ans*=i;
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}