[FJOI2016] 建筑师 题解

标签：begin end 建筑师 int 题解 bmatrix FJOI2016 栋楼

显然有一个 \(dp\) 思路。设 \(f_{i,j}\) 表示现在修了 \(i\) 栋楼，从第一栋楼外侧能看到 \(j\) 栋楼的方案数，显然有：

\[f_{i,j}=\begin{cases}[i=0](j=0)\\f_{i-1,j-1}+(i-1)f_{i-1,j}(j\ne 0)\end{cases} \]

一眼 \(f_{i,j}=\begin{bmatrix}i\\j\end{bmatrix}\)。那么答案即为：

\[\sum_{i=0}^{n-1}\begin{bmatrix}i\\A-1\end{bmatrix}\begin{bmatrix}n-i-1\\B-1\end{bmatrix}\binom ni \]

但这样时间复杂度是 \(O(tn)\) 的，并不能 \(AC\)。考虑组合意义。相当于拿出了 \(A+B-2\) 个圆排列，再挑出了其中的 \(A-1\) 个圆排列。这个式子可以表示为：

\[\begin{bmatrix}n-1\\A+B-2\end{bmatrix}\binom{A+B-2}{A-1} \]

时间复杂度 \(O(n(A+B)+t)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50005,M=105,p=1e9+7;
int t,n,str[N][M*2],C[M*2][M];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t,str[0][0]=1;
    for(int i=1;i<=5e4;i++) for(int j=1;j<=200;j++)
        str[i][j]=(str[i-1][j-1]+str[i-1][j]*(i-1))%p;
    for(int i=0;i<=200;i++){
        C[i][0]=1;
        for(int j=1;j<=min(i,100ll);j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    }while(t--){
        int n,a,b;cin>>n>>a>>b;
        cout<<str[n-1][a+b-2]*C[a+b-2][a-1]%p<<"\n";
    }return 0;
}

标签：begin,end,建筑师,int,题解,bmatrix,FJOI2016,栋楼
From： https://www.cnblogs.com/chang-an-22-lyh/p/18687138/fjoi2016-jian_zhu_shi-tj