【XSY2808】董先生的休闲方案组合数学

题目描述

　　有\(n\)个方案，编号为\(1\ldots n\)。

　　最开始你不知道每个方案的编号。

　　你要按顺序提出这些方案。

　　每一个时刻你要做以下事情：

　　　如果你阅读过下一个方案，就提出这个方案。

　　　否则随机选一个你还没有阅读过的方案，然后阅读这份方案。如果这份方案是你马上要提出的方案，就提出这份方案，否则把这份方案放回到桌子上。

　　问你期望耗时。对\(p^k\)取模。

　　\(p\leq {10}^5,np^k\leq {10}^{18}\)

题解

　　考虑你要在哪种方案上面浪费一个单位的时间，那就是你选择的方案是你下一个要提出的方案。

　　显然你会在其他方案上面浪费两个单位的时间。

　　设\(f_i\)为还有\(i\)个未阅读的方案，提出所有方案需要的时间。

\[\begin{align}
f_n&=f_{n-1}+\frac{1}{n}+2\frac{n-1}{n}\\
f_n&=2n-\sum_{i=1}^n\frac{1}{i}
\end{align}
\]

　　然后直接套用这题的做法就行了。

　　时间复杂度：\(O(pk\log_p n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef __int128 lll;

ll p;

ll mul(ll a,ll b,const ll &c)

{

	return (lll)a*b%c;

}

ll fp(ll a,ll b){ll s=1;for(;b;b>>=1,a*=a)if(b&1)s*=a;return s;}

ll fp(ll a,ll b,const ll &c){ll s=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)s=mul(s,a,c);return s;}

int pri[1000010];

int b[1000010];

ll pw[1000010];

int cnt;

ll ss[100][100];

void getstirling(ll k,const ll &md)

{

	ss[0][0]=1;

	for(int i=1;i<=k;i++)

		for(int j=1;j<=i;j++)

			ss[i][j]=(ss[i-1][j-1]-mul(i-1,ss[i-1][j],md))%md;

}

ll gao(ll n,ll k,const ll &md)

{

	ll s=(n+1)/(k+1);

	ll v=s*(k+1);

	for(ll i=n+1;i>=n-k+1;i--)

		s=mul(s,(i==v?1:i),md);

	return s;

}

void gets(ll *s,ll n,ll k,const ll &md)

{

	s[0]=n;

	for(int i=1;i<=k;i++)

	{

		s[i]=gao(n,i,md);

		for(int j=0;j<i;j++)

			s[i]=(s[i]-mul(ss[i][j],s[j],md))%md;

	}

	s[0]++;

}

ll s1[100];

ll s2[100];

ll g(ll n,const ll &md,ll k)

{

	ll r=n%p;

	getstirling(k,md);

	gets(s1,n/p-1,k,md);

	gets(s2,n/p,k,md);

	ll res=0,s;

	ll t=fp(p,k)-fp(p,k-1)-1;

	for(int i=0;i<k;i++)

	{

		s=0;

		pw[1]=1;

		cnt=0;

		for(int j=1;j<p;j++)

			b[j]=0;

		for(int j=2;j<p;j++)

		{

			if(!b[j])

			{

				pri[++cnt]=j;

				pw[j]=fp(fp(j,i+1),t,md);

			}

			for(int k=1;k<=cnt&&j*pri[k]<p;k++)

			{

				b[j*pri[k]]=1;

				pw[j*pri[k]]=mul(pw[j],pw[pri[k]],md);

				if(j%pri[k]==0)

					break;

			}

		}

		for(int j=1;j<p;j++)

			if(j<=r)

				s=(s+mul(s2[i],pw[j],md))%md;

			else

				s=(s+mul(s1[i],pw[j],md))%md;

		s=mul(s*(i&1?-1:1),fp(p,i),md);

		res=(res+s)%md;

	}

//	fprintf(stderr,"G(%lld, %lld) = %lld\n",n,md,(res+md)%md);

	return res;

}

ll f(ll n,const ll &md,ll k)

{

	if(!n)

		return 0;

	return (g(n,md,k)+f(n/p,md*p,k+1)/p)%md;

}

int main()

{

#ifndef ONLINE_JUDGE

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

	freopen("c.out","w",stdout);

#endif

	ll n,k;

	scanf("%lld%lld%lld",&p,&k,&n);

	const ll md=fp(p,k);

	ll ans=f(n,md,k);

	ans=(2*n-ans)%md;

	ans=(ans+md)%md;

	printf("%lld\n",ans);

	return 0;

}

巴特西

【XSY2808】董先生的休闲方案组合数学

题目描述

题解

代码

最新文章

热门文章

巴特西

【XSY2808】董先生的休闲方案 组合数学

题目描述

题解

代码

最新文章

热门文章

【XSY2808】董先生的休闲方案组合数学