luogu P4562 [JXOI2018]游戏组合数学

LINK：游戏

当L==1的时候容易想到答案和1的位置有关。

枚举1的位置那么剩下的方案为(R-1)! 那么总答案为 (R+1)*R/2(R-1)!

考虑L==2的时候对于一个排列什么时候会终止容易发现是L~R中所有的质数在这个排列中的最后一个位置的影响。

还是枚举这个质数的位置i 此时方案数为 C(i-1,s-1)s!(n-s)!

其中s为L~R之中所有的质数个数.

对于L>2 还是考虑先计算出s的个数刚才是使用了线性筛此时考虑质数不能用了那么可以考虑每个数是否为必要的数。

那么我们从前往后推只需要知道离自己最近的数是谁看一下上一个是不是就能判断当前了。

可以发现要除以一下自己的最小质因子。所以线性筛可以解决。

当然可以直接埃拉筛。统计没被筛到的数字个数即可。复杂度nloglogn

这里使用前者.

const int MAXN=10000010,maxn=110,G=3;

int fac[MAXN],inv[MAXN];

int v[MAXN],p[MAXN];

int L,R;

int cnt,top;

inline int ksm(int b,int p)

{

	int cnt=1;

	while(p)

	{

		if(p&1)cnt=(ll)cnt*b%mod;

		b=(ll)b*b%mod;p=p>>1;

	}

	return cnt;

}

inline void prepare()

{

	fac[0]=fac[1]=1;

	rep(2,R,i)

	{

		fac[i]=(ll)fac[i-1]*i%mod;

		if(!v[i])

		{

			v[i]=i;

			p[++top]=i;

			if(i>=L)++cnt;

		}

		rep(1,top,j)

		{

			if(p[j]>R/i)break;

			int ww=i*p[j];

			v[ww]=p[j];

			if(i<L&&ww>=L)++cnt;

			if(v[i]==p[j])break;

		}

	}

}

inline int C(int a,int b){if(a<b)return 0;return (ll)fac[a]*inv[b]%mod*inv[a-b]%mod;}

int main()

{

	freopen("1.in","r",stdin);

	get(L);get(R);

	prepare();

	if(L==1)put((ll)(1+R)*R/2%mod*fac[R-1]%mod);

	else

	{

		inv[R]=ksm(fac[R],mod-2);

		fep(R-1,0,i)inv[i]=(ll)inv[i+1]*(i+1)%mod;

		int n=R-L+1;

		int ans=0;

		rep(cnt,n,i)ans=(ans+(ll)C(i-1,cnt-1)*fac[cnt]%mod*fac[n-cnt]%mod*i%mod)%mod;

		put(ans);

	}

	return 0;

}

巴特西

luogu P4562 [JXOI2018]游戏组合数学

最新文章

热门文章

巴特西

luogu P4562 [JXOI2018]游戏 组合数学

最新文章

热门文章

luogu P4562 [JXOI2018]游戏组合数学