《算法竞赛进阶指南》0x5C计数DP Gerald & Giant Chess
标签：cst end font name cout 链接 结果 const pac
题目链接：https://www.acwing.com/problem/content/description/308/
给定一个h*w的棋盘，上面有少于2000个黑色格子，其他是白色，问不经过黑色格子从(1,1)走到(h,w)的路线有多少个？
将黑色格子按照(x,y)进行排序，设计f[i]为从(1,1)走到第i个黑色格子不经过其他黑色格子的方案数量，通过容斥原理，只需要计算至少经过一个黑色格子的方案数量，枚举第一个经过的黑色格子就能算出来，预处理出乘法逆元就能快速计算阶乘。
将最后一个点当做黑色格子就可以用f[n+1]代替结果。
注意：操作符定义中按照两个维度进行定义的时候不能用return (x==b.x && y
代码：
#include
#include
#include
using namespace std;
const int N = 2010,M=200010;
const int mod = 1000000007;
typedef long long ll;
#define PII pairstruct node{
int x,y;
bool operator const node &a)const {
if(x==a.x)return ya.y;
else return xa.x;
}
}a[N];
int f[N];
ll jc[M],jcinv[M];
int h,w,n;
ll ksm(ll a,int k){
ll ans=1;
while(k){
if(k&1)ans=ans*a %mod;
a=a*a %mod;
k>>=1;
}
return ans;
}
int C(int n,int m){//%运算和* /是同一个优先级
return jc[n]*jcinv[m]%mod * jcinv[n-m]%mod;
}
int main(){
cin>>h>>w>>n;
for(int i=1;i){
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a+1,a+n+1);
a[n+1].x=h,a[n+1].y=w;
a[0].x=a[0].y=1;
jc[0]=1;
jcinv[0]=1;
for(int i=1;i200000;i++){//预处理阶乘逆元和阶乘
jc[i]=jc[i-1]*i %mod;
jcinv[i]=ksm(jc[i],mod-2);
}
f[0]=1;
for(int i=1;i1;i++){
f[i]=C(a[i].x-1+a[i].y-1,a[i].x-1);
for(int j=1;j){
if(a[j].x>a[i].x || a[j].y>a[i].y)continue;
f[i] = (f[i] - (ll)f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x)) % mod;
}
}
cout1]+mod)%modendl;
return 0;
}
《算法竞赛进阶指南》0x5C计数DP Gerald & Giant Chess
标签：cst end font name cout 链接 结果 const pac
原文地址：https://www.cnblogs.com/randy-lo/p/13444180.html
评论