Zjoi2011看电影（movie）

第一步，打表找规律，发现自己的表连3的小样例都过不去，还不如自己手模，自己手跑了5以下的样例，然后发现毫无规律可言……

第二步，想出一种错误做法，首先n>k必零，人比座都多……然后粘一下图：

基本思想单步容斥，1除去不可行的，后面那一坨求和是用实际意义想的，前i个人恰好从k个位置中，把最后i个给选掉了（包括移动的过程），然后剩下的n-i个人从k个座位中选中前k-i个则不会牺牲，否则GG，还是单步容斥，1除去不死的情况就是牺牲的。

然后化简，把分母化成n！*n^k这种常数，算分子求和，然后是小点，k<=3的，都过了，特别兴奋，准备上高精，结果试了一个3，5，心里一下就凉了，仔细思考一下，发现确实算重了，画了个3，4，发现有的位置由于那个Combine算重了，再改就多步容斥了。

而且这种题输出分数，又是高精，肯定不会是上式那种变态的形式。

第三步，重新打表，发现与（k+1）关系匪浅（因为k=9那一列全是10的倍数……），规律有了。

下面给出正解：

思路有些反人类，我们都是做环题拆环（即环排列），这题需要我们建环，首先在n<=k的前提下，我们再插入第k+1把椅子，是所有椅子构成一个环，这样想一下，就不可能有人没座了（因为会转圈，而人数小于椅子数，肯定人人有座），所以情况数为（k+1）^n，然后根据换排列的知识，肯定有重复情况（即将圆旋转可以得到同一个圆），当然此时你也可以用拆环的思想（刚建完就拆，Orz），不过一般都是除以元素总数，即k+1，现在就是(k+1)^(n-1)，可是我们比原题多了一把椅子，怎么办呢？从剩下的k+1-n把空椅子中抽一把就好了……这样的话就是符合题意的条件，大家可以自己把式子写下来再想想。

总方案k^n没什么问题，那答案就是(k+1)^(n-1)*(k+1-n)/(k^n)喽。

然后向别人询问了高精gcd……其实用不到，做这种分数题小的求gcd，大的直接唯一分解定理拆，具体实现看看代码吧，不太好说，大概就是把分子拆到一个数组里，把分母拆到一个数组里，比较一下，那个数量多就乘到谁身上，高精还是要自己打的好。

ps：一开始以为会因为玄学高精卡时间，结果自家oj跑的还挺快，就没亿进制优化，想打的自己尝试一下吧。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

struct Bint{

    int a[];

    int len;

    void clear(){

        memset(a,,sizeof(a));

        len=;

        a[]=;

    }

    friend void operator *(Bint &x,int y){

        int res=;

        for(int i=;i<=x.len;i++){

            x.a[i]=x.a[i]*y+res;

            res=x.a[i]/;

            x.a[i]%=;

        }

        while(res){

            x.a[++x.len]=res%;

            res/=;

        }

        while(x.a[x.len]==&&x.len>) x.len--;

    }

    void print(){

        for(int i=len;i>=;i--)

            printf("%d",a[i]);

    }

}afz,afm;

int a[],fz[],fm[],n,k,T;

int p[];

bool judge(int x){

    for(int i=;i<=sqrt(x);i++)

        if(x%i==) return ;

    return ;

}

void doprime(){

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

        if(judge(i)) p[++p[]]=i;

}

void multfz(int x){

    for(int i=;i<=p[];i++)

        while(x%p[i]==) {

            fz[i]++;

            x/=p[i];

        }

}

void multfm(int x){

    for(int i=;i<=p[];i++)

        while(x%p[i]==){

            fm[i]++;

            x/=p[i];

        }

}

void work(){

    for(int i=;i<=p[];i++){

        if(fz[i]>fm[i])

            for(int j=;j<=fz[i]-fm[i];j++)

                afz*p[i];

        else if(fz[i]==fm[i]) continue;

        else

            for(int j=;j<=fm[i]-fz[i];j++)

                afm*p[i];

    }

    afz.print();

    putchar(' ');

    afm.print();

    putchar('\n');

}

int main(){

    doprime();

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&k);

        memset(fz,,sizeof(fz));

        memset(fm,,sizeof(fm));

        afz.clear();afm.clear();

        if(n>k){puts("0 1");continue;}

        for(int i=;i<n;i++)

            multfz(k+);

        multfz(k+-n);

        for(int i=;i<=n;i++)

            multfm(k);

    /*    for(int i=1;i<=p[0];i++)

            cout<<fz[i]<<" ";cout<<endl;

        for(int i=1;i<=p[0];i++)

            cout<<fm[i]<<" ";cout<<endl;*/

        work();

    }return ;

}

巴特西

Zjoi2011看电影（movie）

最新文章

热门文章