HDU5794 - A Simple Chess

---

做法：首先的想法就是用總方案數(shù)減去，經(jīng)過(guò)過(guò)障礙的方案數(shù)A。第一個(gè)思路就是容斥，但是顯然不符合數(shù)據(jù)規(guī)模。另一個(gè)思路就是將障礙物從左上到右下排序，dp[i] 表示不經(jīng)過(guò)前i-1個(gè)障礙，到達(dá)第i個(gè)障礙的方案數(shù)。這里定義cal(a,b) 表示從a到b，無(wú)障礙情況下的方案數(shù)，a[i]是排序后的第i個(gè)點(diǎn)，起點(diǎn)st，終點(diǎn)ed，pre(a)表示能到達(dá)a的點(diǎn)集。那么 \(A = \sum_{i=1}^n dp[i]*cal(a[i],ed)\)，現(xiàn)在考慮轉(zhuǎn)移，dp[i] 就是 到達(dá)pre(a[i])中每個(gè)點(diǎn)的不經(jīng)過(guò)任何障礙的方案數(shù)的和，而這個(gè)值與答案類似可以通過(guò)用總方案減去，之前經(jīng)過(guò)過(guò)障礙的方案數(shù)，這些dp值已經(jīng)求出來(lái)了，直接轉(zhuǎn)移即可。cal(a,b) 中需要注意組合數(shù)的計(jì)算過(guò)程。lucas實(shí)現(xiàn)的時(shí)候沒(méi)有判n和m的正負(fù)，RE了很長(zhǎng)一段時(shí)間。。

#include <cstdio> #include <algorithm> typedef long long ll; const int mod = 110119; using namespace std; ll n, m, dp[111], tmp, ans; int r; ll f[mod], rv[mod]; ll C(ll n, ll m) {return n < m ? 0: f[n]*rv[n-m]%mod*rv[m]%mod; } ll lucas(ll n, ll m) {if(n<m || n < 0 || m < 0) return 0;ll ans=1;for(; m; n/=mod, m/=mod) ans = ans*C(n%mod, m%mod)%mod;return ans; } struct node {ll x, y;node(){}node(ll _x, ll _y) {x = _x; y = _y;} }a[111]; bool cmp(node a,node b) {return (a.x + a.y) <= (b.x + b.y); } int inb(node a) {if(a.x < 1 || a.x > n || a.y < 1 || a.y > m) return 0;return 1; } node pre1(node a) {return node(a.x-2LL,a.y-1LL); } node pre2(node a) {return node(a.x-1LL,a.y-2LL); } ll cal(node a, node b) {if( !inb(a) || !inb(b) ) return 0;ll x = b.x - a.x + 1, y = b.y - a.y + 1;if(x == 1 && y == 1) return 1;if( !inb(node(x,y)) ) return 0;if(x + y - 2 < 0) return 0;if( (x+y-2)%3 ) return 0;ll k = (x+y-2)/3LL;ll num = x-k-1;return lucas(k, num); } int main() {rv[0] = rv[1] = f[0] = f[1] = 1;for(int i = 2; i < mod; ++i) {f[i] = f[i-1]*i % mod; rv[i] = -rv[mod%i]*(mod/i)%mod;while(rv[i] < 0) rv[i] += mod;}for(int i = 2; i < mod; ++i) rv[i] = rv[i]*rv[i-1]%mod;int C = 0;while(scanf("%lld %lld %d", &n, &m, &r) != EOF) {for(int i = 1; i <= r; ++i) scanf("%lld %lld", &a[i].x, &a[i].y);sort(a+1, a+1+r, cmp);ans = cal(node(1,1), node(n,m));for(int i = 1; i <= r; ++i) {dp[i] = tmp = 0;for(int j = 1; j < i; ++j) {tmp += dp[j]*cal(a[j],pre1(a[i]))%mod;tmp += dp[j]*cal(a[j],pre2(a[i]))%mod;tmp %= mod;}dp[i] = cal(node(1,1), pre1(a[i]))%mod + cal(node(1,1), pre2(a[i]))%mod - tmp;((dp[i]%=mod) += mod)%=mod;ans -= dp[i]*cal(a[i],node(n,m))%mod;((ans%=mod) += mod)%=mod;}printf("Case #%d: %lld\n",++C,ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9853829.html

總結(jié)

以上是生活随笔為你收集整理的HDU5794 - A Simple Chess的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。