MYF

HDU 5794 A Simple Chess

Posted on | In | | Visitors

题目链接

HDU 5794

题目类型：容斥原理 ＋ Lucas求组合数

题目来源：2016 Multi-University Training Contest 6

题目分析

题目大意

$n*m$的棋盘上，一个棋子要从$(1, 1)$点走到$(n, m)$点，棋子只能向右下的方向移动，类似“马走日”的方法移动，现在棋盘上有一些障碍，棋子无法走到这些有障碍物的地方，问你有多少种方法，从$(1, 1）$走到 $(n, n)$

解析

一开始想的太简单了，觉得只要找到障碍物的点，然后去掉该点的数字即可，在特殊情况下是这样的，但是如果障碍物a影响了某个点b的方案数，然后又在这个b点放置障碍物要怎么办呢？肯定没有这么简单，需要把大情况中的小情况考虑清楚，这样就又变成了一道容斥的问题。将$m$个障碍物排序，然后依次处理，算上一个障碍物对当前障碍物的影响，求出来到达当前障碍物的方案数量。

别人家的题解——HDU 5794 A Simple Chess （容斥+DP+Lucas）

问题一：如何计算路线数

如果不存在任何障碍,从点(x1,y1)到点(x2,y2):

①. 不能到达：由于走的是”L”型路线(类似象棋的马)，所以有可能到不了.

每走一步实际上是移动了三个单位(包括上下方向)，而起点到终点共有(x2-x1) + (y2-y1)个单位.

所以能走到的充分必要条件是：((x2-x1)+(y2-y1)) % 3 == 0 ; 且终点在起点的左下方(x2>x1 && y2>y1).

②. 如果能到达：走的步数是 step = (x2+y2-x1-y1) / 3.

走法有 “L”型{(x,y)=>(x+2,y+1)} 和 “倒L”型{(x,y)=>(x+1,y+2)} 两种.

无论怎么走都至少会在上下两方向上都减1. 所以上下两方向各剩下 s1=x2-x1-step 和 s2=y2-y1-step 个单位.

再用”L”型和”倒L”型去分配这剩下的单位. 即 C(s1+s2, s1) 或 C(s1+s2, s2).

③. 由于坐标范围较大，而取模的p=110119较小且为质数.

所以这里用lucas公式来求组合数.

(一般的：数较小且mod较大时用逆元求组合数，数较大且mod较小时用lucas求组合数)

(由于上述公式中s1 s2有可能为负数，所以lucas里面一定要对负数组合数作特判)(论完美模版的重要性).

问题二：如何考虑障碍物

容斥 + DP：坐标范围较大，只能对障碍位置进行dp：

dp[i]: 从(1,1)到障碍i且不经过其他障碍的路线数.

转移方程：

dp[i] = (起点到障碍i的路线) - Σ(dp[j] * (障碍j到障碍i的路线))

(其中j为位于障碍i左上方的障碍，即j可以通过合法路径到达i. 因此处理时先对障碍坐标排序).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=110119;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int fcnt=120005;
const long long M=110119;
long long fac[fcnt];
long long inv[fcnt];
struct Block{
    ll x, y;
}block[105];
bool cmp(Block a, Block b){
    if (a.x==b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}
ll powMod(ll a, ll b){
    ll ans =1;
    for( a%=mod; b; b>>=1, a = a * a % mod)
        if(b&1)  ans = ans * a % mod;
    return  ans;
}
void init(){
    fac[0] = 1;
    for(int i = 1; i < mod; i++)
        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 n, ll m){
    return  m > n ? 0 : fac[n] * inv[m] % mod * inv[n-m] % mod;
}
ll Lucas(ll n, ll m){// n>m
    if (n<0||m<0||n<m)
        return 0;
    return  m ? (C(n%mod , m%mod) * Lucas(n/mod, m/mod)) % mod : 1;
}
ll dp[105];
int main(){
    init();
    int cas = 1;
    ll n, m, r, dis, step,nn,mm;
    while (scanf("%lld%lld%lld",&n,&m,&r)!=EOF) {
        for (int i=1; i<=r; i++)
            scanf("%lld%lld",&block[i].x,&block[i].y);
        block[r+1].x = n;
        block[r+1].y = m;
        sort(block+1, block+1+r, cmp);
        
        for (int i=1; i<=r+1; i++) {
            dp[i]=0;
            dis = ( block[i].x - 1 ) + ( block[i].y - 1 ) ;
            if (dis % 3) continue;
            step = dis / 3 ;
            nn =  ( block[i].x - 1 - step ) + ( block[i].y - 1 - step);
            mm = block[i].x - 1 - step;
            dp[i] = Lucas(nn, mm);
            
            for (int j=1; j<i; j++) {
                dis = ( block[i].x - block[j].x ) + ( block[i].y - block[j].y ) ;
                if (dis % 3 || block[j].x > block[i].x || block[j].y > block[i].y) continue;
                step = dis / 3 ;
                nn =  ( block[i].x - block[j].x - step ) + ( block[i].y - block[j].y - step);
                mm = block[i].x - block[j].x - step;
                dp[i] = ((dp[i] - Lucas(nn, mm) * dp[j] + mod) % mod + mod ) %mod;
            }
        }
        
        
        printf("Case #%d: %lld\n",cas++,dp[r+1]);
    }
    return 0;
}