Luogu3330 [ZJOI2011]看电影

题面：Luogu

解析

不看题解完全想不到系列。。。
这题的思路是真的神仙，先考虑无解的情况，那么是(N<K)，特判解决。
现在考虑剩下的情况，无非是求合法方案数，再除以总方案数(N^K),假设(K)个座位连成一个环，坐过了(K)号位坐1号位，那么这样不管怎样选，一定能坐下。现在考虑如何判断是否合法，发现如果我们在(K)号为后加一个(K+1)位，若该位置未被坐过，那么方案合法，所以合法方案数是((K+1)^N*(K+1-N)/(K+1))，就是在(K+1)个位置中选(N)个，再在剩下的(K+1-N)选1个，因为是环形，所以还要除以(K+1)消除影响。最后你会发现要用高精。。。