CF838D题解

很厉害的题。

考虑将原本的座位串成一个环，然后加一个节点在 \(1\) 的前面 \(n\) 的后面。

原问题等价为新节点不被座到的方案数。容易发现所有节点被座到和不被座到的方案数相同，所以答案就是 \((2n+2)^m\times\frac{n+1-m}{n+1}\)。

#include<cstdio>
const int mod=1e9+7;
int n,m;
inline int pow(int a,int b=mod-2){
	int ans(1);for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;
}
signed main(){
	scanf("%d%d",&n,&m);printf("%d",1ll*pow(2*n+2,m)*(n+1-m)%mod*pow(n+1)%mod);
}