首页 > 代码库 > 【bzoj4676】 两双手
【bzoj4676】 两双手
http://www.lydsy.com/JudgeOnline/problem.php?id=4767 (题目链接)
题意
求在网格图上从$(0,0)$走到$(n,m)$，其中不经过一些点的路径方案数。
Solution
转换一下就变成了题意中的模型。我们将网格上的起点和不允许经过的点全部看做一类点，用$f[i]$表示从第$i$个点不经过其它点到达终点的路径条数，用$D(i,j)$表示个点之间的路径条数，$T$表示终点。转移：
\begin{aligned} f[i]=D(i,T)-\sum_j D(i,j)*f[j] \end{aligned}
其中$j$在$i$的右上方。然后注意特判一下问题无法转换的情况。
细节
预处理别预处理少了？
代码
// bzoj4767#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=1000;int Ex,Ey,Ax,Ay,Bx,By,na,nb,n,m;LL fac[maxn*maxn],ifac[maxn*maxn],f[maxn];struct point { int x,y; friend bool operator <= (point a,point b) {return a.x<=b.x && a.y<=b.y;}}p[maxn];LL power(LL a,LL b) { LL res=1; while (b) { if (b&1) (res*=a)%=MOD; b>>=1;(a*=a)%=MOD; } return res;}LL C(int n,int m) { return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}bool cmp(point a,point b) { return a.x==b.x ? a.y<b.y : a.x<b.x;}LL D(point a,point b) { return C(b.x+b.y-a.x-a.y,b.x-a.x);}int main() { scanf("%d%d%d",&Ex,&Ey,&n); scanf("%d%d%d%d",&Ax,&Ay,&Bx,&By); if ((Ex*By-Ey*Bx)%(Ax*By-Ay*Bx)) {puts("0");return 0;} na=(Ex*By-Ey*Bx)/(Ax*By-Ay*Bx); nb=Bx ? (Ex-Ax*na)/Bx : (Ey-Ay*nb)/By; if (p[0].x<0 || p[0].y<0) {puts("0");return 0;} for (int ca,cb,x,y,i=1;i<=n;i++) { scanf("%d%d",&x,&y); if ((x*By-y*Bx)%(Ax*By-Ay*Bx)) continue; ca=(x*By-y*Bx)/(Ax*By-Ay*Bx); cb=Bx ? (x-Ax*ca)/Bx : (y-Ay*ca)/By; if (0<=ca && ca<=na && 0<=cb && cb<=nb) p[++m]=(point){ca,cb}; } sort(p+1,p+1+m,cmp); n=na+nb; p[m+1]=(point){na,nb};p[0]=(point){0,0}; fac[0]=1;for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD; ifac[n]=power(fac[n],MOD-2); for (int i=n;i>=1;i--) ifac[i-1]=ifac[i]*i%MOD; for (int i=m;i>=0;i--) { f[i]=D(p[i],p[m+1]); for (int j=i+1;j<=m;j++) if (p[i]<=p[j]) (f[i]+=MOD-D(p[i],p[j])*f[j]%MOD)%=MOD; } printf("%lld",f[0]); return 0;}
【bzoj4676】 两双手
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。