HDU 5794 A Simple Chess(허용 원리 + Lucas 정리 + dp)

A Simple Chess

문제 설명
n*m 바둑판이 있는데, 바둑알 한 개가 (1,1)칸에서 (n,m)칸으로 이동해야 한다.이 바둑알은 좌표 (x1, y1) 의 칸에서 칸 (x2, y2) 으로 뛰어넘을 수 있으며, 단지 다음과 같다.
(x2-x1)^2+(y2-y1)^2=5 x2>x1,y2>y1
바둑판에 r개의 칸이 있고 장애물이 있어서 바둑알은 장애물이 있는 칸에 떨어질 수 없다.이 바둑알이 기점에서 종점까지 모두 몇 가지 방안이 있는지 계산해 보세요.
입력 형식
몇 개의 그룹 데이터(<=25조)가 있는데 각 그룹의 데이터에 대해 형식은 다음과 같다. 한 줄, 세 개의 정수 n, m, r 다음 r줄, 한 줄에 두 개의 정수는 장애물이 있는 칸의 좌표를 나타낸다.
출력 형식
각 그룹의 데이터에 대해 한 줄, 한 정수를 출력하여 원하는 방안의 수를 나타낸다.mod 110119
샘플 입력 1
1 1 0 3 3 0 4 4 1 2 1 4 4 1 3 2 7 10 2 1 2 7 1
샘플 출력 1
1 0 2 1 5
샘플 입력 2
58939239 79926962 4 28255565 36535194 51497377 67322260 48931736 62290476 23383627 30097072
샘플 출력 2
9061
프롬프트
100% 데이터: 1≤n, m≤10^18, 0≤r≤100(1,1)칸에 장애가 없습니다.
편의를 위해 제목의 x, yx, y 좌표를 모두 1로 줄여 (0,0)(0,0)에서 (n-3-1, m-31)(n-3-1, m-3-1)로 변경한다.
만약 장애를 고려하지 않는다면 (0,0)(0,0)에서 (x,y)(x,y)(x,y)까지의 방안 수는 하나의 조합수이다. 이것은 비교적 잘 추측할 수 있다. 바로 C2x이다. 즉, y3x+y3 C+y 3 x-3 x-3 x-3이다. (x,y)(x,y)는 도달할 수 있고 x+y만 도달할 수 있다.
장애의 수가 비교적 적고 용납을 고려하여 F[i] F[i]로 하여금 (1,1)(1,1)에서 출발하여 지나는 첫 번째 장애는 ii의 장애이다. 그러면 ii의 왼쪽 아래에 있는 모든 장애물에 대해
F[i]=C2xi−yi3xi+yi3−∑jF[j]×C2tx−ty3tx+ty3,tx=xi−xj,ty=yi−yj F [ i ] = C x i + y i 3 2 x i − y i 3 − ∑ j F [ j ] × C t x + t y 3 2 t x − t y 3 , t x = x i − x j , t y = y i − y j
직접 기억화 검색을 하고 폭력적으로 그 점들을 왼쪽 아래에 열거하면 된다.
조합수
Lucas L u c a s 처리
이 가능하다, ~할 수 있다,...
0 0, 이 때도 가지 못한다는 것을 의미하기 때문에 되돌아가야 한다
0 0
또 종점이 장애라면 답도 주의해야 한다
0 0
총 시간 복잡도 O (n2×???) O ( n 2 × ? ? ? ) ,그래도 금방.
코드:

#include
#include
#include
#include
#define N 105
#define ll long long
using namespace std;
const ll mod=110119;
ll n,m,r,F[N],X[N],Y[N],fac[110220],inv[110220];
bool mark[N];
ll C(ll a,ll b)
{
    if(areturn 0;
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
ll Lucas(ll a,ll b)
{
    if(areturn 0;
    if(a<0||b<0)return 0;
    if(b==0||a==0)return 1;
    return Lucas(a/mod,b/mod)*C(a%mod,b%mod)%mod;
}
ll DP(ll p)
{
    ll i,j;
    if(F[p]!=-1)return F[p];
    if(mark[p])return F[p]=0;
    F[p]=Lucas((X[p]+Y[p])/3,(2*Y[p]-X[p])/3);
    for(i=1;i<=r;i++)
    if(X[i]if(mark[i])continue;
        F[p]-=DP(i)*Lucas((X[p]+Y[p]-X[i]-Y[i])/3,(2*(Y[p]-Y[i])-X[p]+X[i])/3)%mod;
        F[p]%=mod;
    }
    F[p]+=mod;F[p]%=mod;
    return F[p];
}
int main()
{
    ll i,j,k,x,y;bool f;
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(i=2;i<=mod;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    for(i=2;i<=mod;i++)inv[i]=inv[i]*inv[i-1]%mod;
    while(scanf("%lld%lld%lld",&n,&m,&r)!=EOF)
    {
        f=0;
        for(i=1;i<=r;i++)
        {
            scanf("%lld%lld",&X[i],&Y[i]);
            if(X[i]==n&&Y[i]==m)f=1;
        }
        if(f){puts("0");continue;}
        for(i=1;i<=r;i++)X[i]--,Y[i]--;
        X[++r]=n-1;Y[r]=m-1;
        for(i=1;i<=r;i++)mark[i]=(X[i]+Y[i])%3!=0;
        memset(F,-1,sizeof(F));
        printf("%lld
",DP(r));
    }
}