找規律+Lucas定律_______A Simple Chess(hdu 5794 2016多校第六場)

題目位址：HDU 5794

題目意思：

起始點（1,1），要到達（n，m），下一步（x2，y2），這一步（x1，y1），需滿足（x2-x1）^2 +（y2-y1）^2 = 5，且 x2>x1 、y2>y1。中間還有r 個障礙點，問最終有多少種方法到達（n，m）。n、m高達10^18，r最多100。

分析：如果不加入障礙點很容易就可以知道是個組合問題。但是加入障礙點後我們隻需要從所有情況中剔除掉經過障礙點的路徑，那麼我們定義dp[i]表示從(1,1)不經過任何障礙走到第i個障礙位置的所有途徑，很顯然這個問題就是題目原問題的子問題。那麼所有經過障礙的路徑我們可以看作對于所有障礙的1~r,不經過任何障礙到達目前障礙然後使用任意路徑到達終點。這樣枚舉可以保證經過障礙路徑不重不漏。

代碼：

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
#include <cstdlib>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL MOD = 110119;
LL mmy[110];
struct point
{
    LL x,y;
}p[110];
LL r;
LL n,m;
LL all[MOD+5],f[MOD+5];

LL C(LL n, LL m)
{
    if(m > n) return 0;
    if (m==0) return 1;
    if (m<0) return 0;
    return f[n]*all[f[m]]%MOD*all[f[n-m]]%MOD;
}
LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % MOD, m % MOD) * Lucas(n / MOD, m / MOD) % MOD;
}
void init()
{
    f[1]=f[0]=all[1]=1;
    for(int i=2; i<=MOD; ++i)
    {
        f[i]=f[i-1]*i%MOD;
        all[i]=all[MOD%i]*(MOD-MOD/i)%MOD;
    }
}
bool cmp(point a,point b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
int visit[110];
int main()
{
    LL _case = 0;
    init();
    while(scanf("%I64d%I64d%I64d",&n,&m,&r)!=EOF)
    {
        int flag = 0;
        memset(visit,0,sizeof(visit));
        for(LL i = 0 ; i < r ; i ++)
        {
            scanf("%I64d%I64d",&p[i].x,&p[i].y);
            if(p[i].x == n && p[i].y == m) flag = 1;
            p[i].x --;
            p[i].y --;
        }
        int tot = 0;
        for(int i = 0 ; i < r; i ++)
            for(int j = i + 1 ; j < r ; j ++)
                if(p[i].x == p[j].x && p[i].y == p[j].y)visit[j] = 1;
        for(int i = 0 ; i < r; i ++)
            if(visit[i] == 0) p[tot++] = p[i];
        r = tot;

        p[r].x = n - 1;
        p[r].y = m - 1;
        r++;
        sort(p,p+r,cmp);
        if(r >= 2 && p[r-2].x == p[r-1].x && p[r-2].y == p[r-1].y)
        {
            mmy[r-1] = 0;
        }
        else
        {
            memset(mmy,0,sizeof(mmy));
            for (int i=0; i<r; i++)
            {
                if ((p[i].x+p[i].y)%3==0)
                {
                    LL di=(p[i].x+p[i].y)/3;
                    LL gao=min(p[i].x,p[i].y)-di;
                    mmy[i]=Lucas(di,gao);

                    for (int j=0;j<i;j++)
                    {
                        if (p[j].y<p[i].y&&p[j].x<p[i].x)
                        {
                            LL xx=p[i].x-p[j].x,yy=p[i].y-p[j].y;
                            if ((xx+yy)%3==0)
                            {
                                LL dd=(xx+yy)/3;
                                LL gg=min(xx,yy)-dd;
                                mmy[i]-=(Lucas(dd,gg)*mmy[j])%MOD;
                                mmy[i]=(mmy[i]+MOD)%MOD;
                            }
                        }
                    }
                }
            }
        }
        printf("Case #%I64d: %I64d\n",++_case,mmy[r-1]);
    }
    return 0;
}