codeforces 838D D. Airplane Arrangements 构造法 推公式

题意：航空公司卖机票。飞机座位是1~n的，卖m张票，m小于等于n，每张票上有三个信息，票号 i，座位号 j，登机入口 k，登机入口指的是从机头进入或者是从机尾进入。

乘客登飞机规则：

1. 乘客按照机票的编号从小到大依次登机。

2. 乘客登飞机时，从票上指定的入口进入，径直走到自己的位置处，如果有人，就看下一个位置有没有人，直到找到第一个空座位，便入座，如果一直走到头都没有位置，该乘客就会暴走。

航空公司想知道它有多少种印票方式，使得乘客不暴走。其中，票上的座位号可以重复。两种印票方式不同当且仅当两套票中存在票号为 i 的票，票上的信息不完全一样。

解法：构造数学模型推公式。

考虑非法情况，可以看成是有一个乘客从飞机头走到飞机尾，在一个虚拟位置就座；或者从飞机尾走到飞机头，在一个虚拟位置就座。这两个位置是等价的，我们把它看成是第 n+1 个位置。这样，这个位置就把飞机串成了一个长度为 n+1 的环。合法的方案就是环上该位置为空时所有乘客就座的方式。

考虑非法和合法情况，这个环上，乘客就座方式总情况为 (2*(n+1))^m。因为每个位置是等价的，环上要使某一特定位置为空的情况占总情况的 (n+1-m)/(n+1)，故答案就是 (2*(n+1))^m * (n+1-m)/(n+1)，答案比较大，快速幂一下；模的是质数，用一下逆元。

#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long ksm(long long x,long long n) {
    long long ret=1;
    while (n) {
        if (n&1)
            ret=ret*x%mod;
        n>>=1;
        x=x*x%mod;
    }
    return ret;
}
long long n,m;
int main()
{
    cin>>n>>m;
    cout<<ksm(2LL*(n+1),m)*(n+1-m)%mod*ksm(n+1,mod-2)%mod;
    return 0;
}