【题解】餐馆

WYXkk · 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;
}

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

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

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

#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) 的标算和一群大学生