自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:16:39，当前版本为作者最后更新于2020-01-17 19:12:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 餐馆

看到这题，我们发现并没有什么很好用的性质。推式子也很难推。

所以，我们当然是找规律了！

打暴力要注意的：

• 一个区间 $[l,r]$ 被选中的概率是 $\dfrac1{nr}$。
• 为了更好看出规律，我们需要用分数存储答案，记得约分。

然后就是暴力了：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct frac//分数类，看不懂没关系 
{
	public:
		ll x,y;//存储x/y
	private:
		ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}//用于约分 
		void yf(){if(y<0)x=-x,y=-y;ll a=gcd(abs(x),y);x/=a,y/=a;}//约分 
	public:
		frac(ll x=0,ll y=1):x(x),y(y){yf();}
		double todb(){return (double)x/(double)y;}
		frac operator=(frac b){x=b.x,y=b.y;return *this;}
};
frac operator+(frac a,frac b){return frac(a.x*b.y+a.y*b.x,a.y*b.y);}
frac operator-(frac a){return frac(-a.x,a.y);}
frac operator-(frac a,frac b){return a+(-b);}
frac operator*(frac a,frac b){return frac(a.x*b.x,a.y*b.y);}
frac operator/(frac a,frac b){return frac(a.x*b.y,a.y*b.x);}
frac operator+=(frac& a,frac b){return a=a+b;}
frac operator-=(frac& a,frac b){return a=a-b;}
frac operator*=(frac& a,frac b){return a=a*b;}
frac operator/=(frac& a,frac b){return a=a/b;}
//加减乘除各种运算 
bool operator>(frac a,frac b){return a.x*b.y>b.x*a.y;}
bool operator<(frac a,frac b){return b>a;}
bool operator>=(frac a,frac b){return !(b>a);}
bool operator<=(frac a,frac b){return !(a>b);}
bool operator==(frac a,frac b){return !(a<b)&&!(b<a);}
bool operator!=(frac a,frac b){return (a<b)||(b<a);}
//比较 
//其实上面有些不会用到 

int L[20],R[20];//存储区间 
int n,k;
bool cross(int l1,int r1,int l2,int r2){return r1>=l2&&r2>=l1;}//区间相交 
frac ans(0,1);
void dfs(int t,frac p)
{
	if(t>k) {ans+=p;return;}
	for(int r=1;r<=n;++r) for(int l=1;l<=r;++l)
	{
		bool flg=true;
		for(int i=1;i<t;++i) if(cross(l,r,L[i],R[i])) flg=false;
		if(!flg) continue;
		L[t]=l;R[t]=r;dfs(t+1,p*frac(1,n*r));
	}
}
int main()
{
	cin>>n>>k;
	dfs(1,frac(1,1));
	printf("Ans=%lld/%lld",ans.x,ans.y);
	return 0;
}

接下来就是根据结果找规律啦！

$k=1$：$\dfrac11\;\dfrac11\;\dfrac11\;\cdots$ 所以 $k=1$ 时答案为 $1$。

$k=2$：$\dfrac01\;\dfrac14\;\dfrac13\;\dfrac38\;\dfrac25\;\cdots$ 似乎没什么规律？但是如果我们适当的反约分一下：

$k=2$：$\dfrac02\;\dfrac14\;\dfrac26\;\dfrac38\;\dfrac4{10}\;\cdots$ 规律就明显多了吧：$Ans=\dfrac{n-1}{2n}$

$k=3$：$\dfrac{0}{1}\;\dfrac{0}{1}\;\dfrac{1}{27}\;\dfrac{1}{16}\;\dfrac{2}{25}\;\dfrac{5}{54}\;\dfrac{5}{49}\;\dfrac{7}{64}\;\cdots$ 总之我看出了规律：$Ans=\dfrac{(n-1)(n-2)}{6n^2}$

进过一系列推算我们最终得出了规律：$Ans=\dfrac{(n-1)(n-2)\cdots(n-k+1)}{k!\times n^{k-1}}=\dfrac{C_n^k}{n^k}$

然后，就没有然后了。按照式子计算即可。时间复杂度 $O(k)$。

$\texttt{code:}$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const ll p=1000000007;
ll qp(ll a,ll b){if(!b)return 1;ll w=qp(a,b>>1);w=w*w%p;return b&1?w*a%p:w;}
ll ni(ll a){return qp(a,p-2);}
ll n,k,a=1,b=1;
int main()
{
	cin>>n>>k;
	F(i,1,k) a=a*(n+1-i)%p,b=(b*i)%p*n%p;
	cout<<a*ni(b)%p;
	return 0;
}

一些题外话

部分分是瞎出的，希望不要妨碍思考正解。

由某场我参加的 ACM 的 H 改编而来，原题 $k=2,n\le 10^6$，然后我成功用 $O(1)$ 的方法吊打 $O(n)$ 的标算和一群大学生