题解——P3330 [ZJOI2011]看电影

· · 题解

题目传送门

前排广告

省流：

\operatorname{ans}=\dfrac{(k+1)^{n-1}(k+1-n)}{k^n}

说说我自己这个式子的理解吧。

首先，如果人数多于座位数，即 n>k，是绝对无法达成“都有座位”的，直接特判输出。

接着，一个事件的概率=符合条件的情况数/总情况数，那么这个总情况数是非常好考虑的，n 个人等概率的从 [1,k] 中选取一个，情况数自然是 k^n。

然后来看符合条件的情况数，注意到题目中提到“如果当前位置已经有人则向下一个位置以此类推”，而我们并不确定开始选择的位置究竟是什么，不如添加一个 k+1 号椅子并连成一个环，排除其他条件不谈，这 (k+1) 个椅子的情况数为 (k+1)^n，然而是存在重复情况的。例如 {1,3,2,4} 与 {2,4,1,3} 分别首尾相连成环以后，都是形如 {1,3,2,4,(1}) 的，也就是说这两种情况是等价的。而成环的连接点有 (k+1) 个，去重后就有 (k+1)^{n-1} 种情况。

接下来是个人认为最难的地方了，这个 (k+1-n) 是怎么得来的？为什么要连成一个环？

因为这里考虑的是符合条件“都有座位”的情况数，那么就要保证成功，方法是尽可能让每个人向右找座位的容错更高，但显然这个开始点是不确定的，我们连成一个环后，对于每个情况单独考虑，所有没有坐人的地方都可以删去并断开成正常的序列。因此选 n 个座位后剩下的是 k+1-n 个座位，也就是可以断成 k+1-n 种不同的序列。

对上述解释一句话概括：连成环后忽略编号，哪里为空断开哪里，哪里就是 k+1 把椅子。

然而需要一个高精度，因为式子中 (k+1)^{n-1} 与 k^n 是无法化简，只要看 n+1-k 和 k^n 就可以了，这里会发现，前一个数字是个低精度，而高精取模低精后是低精度，所以麻烦的高精 \gcd 其实可以拆分成一次高精取模低精和低精 \gcd 就可以了。

其他的看代码就能理解了。

int t;
struct largenum{
    int num[10005];
    inline void scan(){
        char s[10005];
        scanf("%s",s+1);
        int len=strlen(s+1);
        for(int i=len;i>=1;i-=4){
            int j=max(i-3,1);
            int sum=0;
            while(j<=i){
                sum=sum*10+(s[j++]-'0');
            }
            num[++num[0]]=sum;
        }
    }
    inline void print(){
        printf("%d",num[num[0]]);
        for(int i=num[0]-1;i>=1;i--){
            printf("%04d",num[i]);
        }
        printf(" ");
    }
    largenum operator *(const largenum &tmp)const{
        largenum res;
        memset(res.num,0,sizeof(res.num));
        res.num[0]=num[0]+tmp.num[0];
        for(int i=1;i<=num[0];i++){
            for(int j=1;j<=tmp.num[0];j++){
                res.num[i+j-1]+=num[i]*tmp.num[j];
                res.num[i+j]+=res.num[i+j-1]/base;
                res.num[i+j-1]%=base;
            }
        }
        while(res.num[res.num[0]]) res.num[0]++;
        while(!res.num[res.num[0]]&&res.num[0]>1) res.num[0]--;
        return res;
    }
    largenum operator *(const int &tmp)const{
        largenum res;
        memset(res.num,0,sizeof(res.num));
        res.num[0]=num[0];
        int laz=0;
        for(int i=1;i<=res.num[0];i++){
            res.num[i]=num[i]*tmp+laz;
            laz=res.num[i]/base;
            res.num[i]=res.num[i]%base;
        }
        while(laz){
            res.num[++res.num[0]]=laz%base;
            laz/=base;
        }
        while(res.num[res.num[0]]) res.num[0]++;
        while(!res.num[res.num[0]]&&res.num[0]>1) res.num[0]--;
        return res;
    }
    int operator %(const int &tmp)const{
        int res=0;
        for(int i=num[0];i>=1;i--){
            res=(res*base+num[i])%tmp;
        }
        return res;
    }
    largenum operator /(const int &tmp)const{
        largenum res;
        memset(res.num,0,sizeof(res.num));
        res.num[0]=num[0];
        ll laz=0;
        for(int i=res.num[0];i>=1;i--){
            res.num[i]=(laz*base+num[i])/tmp;
            laz=(laz*base+num[i])%tmp;
        }
        while(!res.num[res.num[0]]&&res.num[0]>1) res.num[0]--;
        return res;
    }
}ans1,ans2,tmp;
inline largenum q_pow(largenum x,int p){
    largenum res;
    memset(res.num,0,sizeof(res.num));
    res.num[0]=res.num[1]=1;
    while(p){
        if(p&1){
            res=res*x;
        }
        x=x*x;
        p>>=1;
    }
    return res;
}
inline int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
int n,k,m;
int main(){
    t=read();
    while(t--){
        n=read(),k=read();
        m=k+1-n;
        if(n>k){
            printf("0 1\n");
            continue;
        }
        memset(ans1.num,0,sizeof(ans1.num));
        memset(ans2.num,0,sizeof(ans2.num));
        ans1.num[0]=ans2.num[0]=1;
        ans1.num[1]=k+1,ans2.num[1]=k;
        ans1=q_pow(ans1,n-1);
        ans2=q_pow(ans2,n);
        ans1=ans1*m;
        //ans1.print();
        //ans2.print();
        tmp=ans2;
        int g=tmp%m;
        //printf("\n%d\n",g);
        g=gcd(m,g);
        //printf("%d\n",g);
        ans1=ans1/g;
        //printf("%d\n",m);
        ans1.print();
        ans2=ans2/g;
        ans2.print();
        printf("\n");
    }
    return 0;
}