第一步，打表找规律，发现自己的表连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[6000]; int len; void clear(){ memset(a,0,sizeof(a)); len=1; a[1]=1; } friend void operator *(Bint &x,int y){ int res=0; for(int i=1;i<=x.len;i++){ x.a[i]=x.a[i]*y+res; res=x.a[i]/10; x.a[i]%=10; } while(res){ x.a[++x.len]=res%10; res/=10; } while(x.a[x.len]==0&&x.len>1) x.len--; } void print(){ for(int i=len;i>=1;i--) printf("%d",a[i]); } }afz,afm; int a[6000],fz[6000],fm[6000],n,k,T; int p[6000]; bool judge(int x){ for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0; return 1; } void doprime(){ for(int i=2;i<=200;i++) if(judge(i)) p[++p[0]]=i; } void multfz(int x){ for(int i=1;i<=p[0];i++) while(x%p[i]==0) { fz[i]++; x/=p[i]; } } void multfm(int x){ for(int i=1;i<=p[0];i++) while(x%p[i]==0){ fm[i]++; x/=p[i]; } } void work(){ for(int i=1;i<=p[0];i++){ if(fz[i]>fm[i]) for(int j=1;j<=fz[i]-fm[i];j++) afz*p[i]; else if(fz[i]==fm[i]) continue; else for(int j=1;j<=fm[i]-fz[i];j++) afm*p[i]; } afz.print(); putchar(' '); afm.print(); putchar(' '); } int main(){ doprime(); scanf("%d",&T); while(T--){ scanf("%d%d",&n,&k); memset(fz,0,sizeof(fz)); memset(fm,0,sizeof(fm)); afz.clear();afm.clear(); if(n>k){puts("0 1");continue;} for(int i=1;i<n;i++) multfz(k+1); multfz(k+1-n); for(int i=1;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 0; }