当前位置: 代码迷 >> 综合 >> HDU 5794 A Simple Chess (DP+lucas定理)
  详细解决方案

HDU 5794 A Simple Chess (DP+lucas定理)

热度:49   发布时间:2023-11-15 13:12:04.0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5794

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<ll,ll>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int  maxn =2e5+5;
const int mod=110119;
const int inv2=499122177;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}/*
题目大意:给定一个二维地图的维度,
地图上有若干个陷阱,陷阱是不能走入的,
起点在(1,1),终点在(n,m)其只能在右上方,
走(1,2)或者(2,1)这样的方格步进,
问从起点到终点的方案数是多少。题目分析:对于从起点到终点(不管障碍物),方案数列个方程就好了,
假设进行了x次(1,2),y次(2,1),那么可以解出来x和y的具体表达,
组合数就是C(x+y,y)。
再考虑障碍物,用DP的思想去删除其障碍点的影响,
由于障碍点的数量十分少,二重循环即可,
对于第i个障碍点,其初始贡献是从起点到这里的数量,
对于满足大小关系的i和j障碍点,i要减去从i到j的组合数*dp[j]。
这是为了给以后要同时用到i和j的点消去重复度。
比如既然从j可以走到i,那么i到目标点的方案其因子dp[i]就不能包含经过j的方案,
这种情况会在计算j的时候考虑进去。求组合数的时候用lucas定理搞下即可。
时间复杂度:O(m*m+110119....)*/int ca=0;
ll n,m,r,x,y;
pair<ll,ll> pp[105];
ll fac[mod+5],inv[mod+5],dp[105];
void init(){fac[0]=1LL;rep(i,1,mod) fac[i]=fac[i-1]*i%mod;inv[mod-1]=powmod(fac[mod-1],mod-2);for(int i=mod-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll p,ll q){///求组合数if(q>p||p<0||q<0)return 0LL;if(q==0||p==q) return 1LL;return fac[p]*inv[q]%mod*inv[p-q]%mod;
}
///n,m较大时需要用到lucas定理
ll lucas(ll p,ll q){if(2*q<p||2*p<q) return 0LL;ll tx=p,ty=q;if( (2*q-p)%3 || (2*p-q)%3 ) return 0LL;p=(2*ty-tx)/3,q=(2*tx-ty)/3;p+=q;ll ans=1;while(p&&q){ll a=p%mod,b=q%mod;if(a<b) return 0LL;ans=ans*C(a,b)%mod;p/=mod;q/=mod;}return ans;
}int flag;
int main(){init();///初始化while(scanf("%lld%lld%lld",&n,&m,&r)!=EOF){n--,m--,flag=0;rep(i,0,r){scanf("%lld%lld",&x,&y);x--,y--;pp[i]=make_pair(x,y);if(x==n&&y==m) flag=1;}pp[r++]=make_pair(n,m);sort(pp,pp+r);///排序mst(dp,0);///DP过程rep(i,0,r) dp[i]=lucas(pp[i].fi,pp[i].se);rep(i,0,r) rep(j,0,i) if(pp[i].fi>pp[j].fi&&pp[i].se>pp[j].se)dp[i]=(dp[i]-dp[j]*lucas( pp[i].fi-pp[j].fi , pp[i].se-pp[j].se )%mod+mod)%mod;printf("Case #%d: ",++ca);if(flag) puts("0");///以防终点就是obstracleelse printf("%lld\n",dp[r-1]);}return 0;
}

 

  相关解决方案