[CF559C] Gerald and Giant Chess（动态规划）

题目链接

题解

先介绍一个东西：多重集(multiset)的全排列（这里是特殊情况，即选的元素个数不超过任意集合中元素个数的情况）
我们定义集合的集合为多重集，比如我有 $encoding="application/x-tex">a_1</annotation></semantics></math>$ 个 $1$ ， $encoding="application/x-tex">a_2</annotation></semantics></math>$ 个 $2$ …… 个。
那么写成多重集就是 $\left\{\left\{a_1·1\right\},\left\{a_2·2\right\},\cdots,\left\{a_n·n\right\}\right\}$
如果我们要从中取 $k$ 个数（上面说了， $k$ 不大于 $encoding="application/x-tex">a_i</annotation></semantics></math>$ ），那么有多少种方案呢？

具体证明请移步至维基百科，这里直接给出结论：

也就是

encoding="application/x-tex">C_{n+k-1}^{n+1}</annotation></semantics></math>

那么这题其实如果我们把每一行看成一个集合，元素个数就是列数-1（因为我们最终目标是走到右下角，而如果走到了右侧，再走到右下角的方案已经确定，随意等价于走到右侧），如果没有黑格子的话，我们要选的元素个数也是列数-1，答案就是 $encoding="application/x-tex">C_{H+W-2}^{H-1}</annotation></semantics></math>$

而如果有黑格子，我们可以统计出不合法的方案数减去即可。

所谓不合法，就是在路径上走到过黑格子，为了避免重复，我们设 $f [i]$ 为只经过第 $i$ 个黑格子的方案数，对于它的求法，可以把它当成右下角，求贡献，对于区域内的黑格子，根据乘法原理，它们产生的不合法的方案数为 $encoding="application/x-tex">f[j]\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j}</annotation></semantics></math>$ 即原点到他的方案数乘上以第 $j$ 个黑格子为左上角，第 $i$ 个黑格子为右下角的子矩阵的方案数。

具体实现时可以按照坐标排个序，减少枚举量，设右下角为第 $n + 1$ 个黑格子，方便计算答案，还有就是不要弄混横纵坐标。

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int h,w,n,ans; 
pair<int,int>node[2003];
ll fact[200003];
ll inv[200003];
ll f[2003];

ll qpow(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

void pre(int n){
    fact[0]=1;
    for(int i=1;i<=n;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    inv[n]=qpow(fact[n],MOD-2,MOD);
    for(int i=n-1;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%MOD;
    }
}

int C(int n,int m){
    if(n==m)return 1; 
    return fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}

int main(){
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++){
        cin>>node[i].x>>node[i].y;
    }
    pre(200000);
    node[n+1].x=h,node[n+1].y=w;
    sort(node+1,node+2+n);
    for(int i=1;i<=n+1;i++){
        f[i]=C(node[i].x+node[i].y-2,node[i].x-1);
        for(int j=1;j<i;j++){
            if(node[i].x<node[j].x||node[i].y<node[j].y)continue;
            f[i]=(f[i]-(ll)f[j]*C(node[i].y-node[j].y+node[i].x-node[j].x,node[i].x-node[j].x)%MOD)%MOD;
        }
        while(f[i]<0)f[i]+=MOD;
    }
    cout<<f[n+1]<<endl;
    return 0;
}

#include<bits/stdc++.h>

#define x first

#define y second

using namespace std;

typedef long long ll;

const int MOD=1e9+7;

int h,w,n,ans;

pair<int,int>node[2003];

ll fact[200003];

ll inv[200003];

ll f[2003];

ll qpow(ll a,ll b,ll p){

ll ans=1;

while(b){

if(b&1)ans=ans*a%p;

a=a*a%p;

b>>=1;

}

return ans;

}

void pre(int n){

fact[0]=1;

for(int i=1;i<=n;i++){

fact[i]=fact[i-1]*i%MOD;

}

inv[n]=qpow(fact[n],MOD-2,MOD);

for(int i=n-1;i>=0;i--){

inv[i]=inv[i+1]*(i+1)%MOD;

}

int C(int n,int m){

if(n==m)return 1;

return fact[n]*inv[m]%MOD*inv[n-m]%MOD;

}

int main(){

cin>>h>>w>>n;

for(int i=1;i<=n;i++){

cin>>node[i].x>>node[i].y;

}

pre(200000);

node[n+1].x=h,node[n+1].y=w;

sort(node+1,node+2+n);

for(int i=1;i<=n+1;i++){

f[i]=C(node[i].x+node[i].y-2,node[i].x-1);

for(int j=1;j<i;j++){

if(node[i].x<node[j].x||node[i].y<node[j].y)continue;

f[i]=(f[i]-(ll)f[j]*C(node[i].y-node[j].y+node[i].x-node[j].x,node[i].x-node[j].x)%MOD)%MOD;

}

while(f[i]<0)f[i]+=MOD;

}

cout<<f[n+1]<<endl;

return 0;

}

题解

代码

分享到微信

发送评论 编辑评论

发送评论编辑评论