答案是
(K+1)n−1∗(K+1−n)Kn 证明很妙啊先加上一个位置并看成一个环，那么方案数就是 (K+1)n ，并且可以保证一定合法，因为是环，又因为是环可以转有 K+1 个方案重复了，所以实际上是 (K+1)n−1 。 拆掉一个空座位回到原问题，因为是空位，所以一定没有人跨过去，任何一个空位都可拆，那么拆的方案数是 K+1−n
分解什么质因数 K 和K 1是互质的啊
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define cl(x) memset(x,0,sizeof(x)) #define read(x) scanf("%d",&(x)) using namespace std; inline int Gcd(int a,int b){ return !b?a:Gcd(b,a%b); } const int CON=100000; struct Int{ int a[1000]; Int(int x=0){ cl(a); a[++*a]=x; } Int &operator *=(int t){ for (int i=1;i<=*a;i++) a[i]*=t; for(int i=1;i<=*a+10;i++) a[i+1]+=a[i]/CON,a[i]%=CON; for(int i=*a+10;i;i--) if (a[i]) { *a=i; return *this; } } void print(){ printf("%d",a[*a]); for(int i=*a-1;i;i--) printf("d",a[i]); } }A,B; int main(){ int Q,n,K; freopen("movie.in","r",stdin); freopen("movie.out","w",stdout); read(Q); while (Q--){ read(n); read(K); if (K<n) { printf("0 1\n"); continue; } A=Int(1); B=Int(1); int x=K+1-n,g; for(int i=1;i<=n-1;i++) g=Gcd(K,x),x/=g,A*=K+1,B*=K/g; g=Gcd(K,x),x/=g,A*=x,B*=K/g; A.print(); putchar(' '); B.print(); putchar('\n'); } return 0; }