[수론+dp] codeforces559C Gerald and Giant Chess

전송문
제목 설명: h*w(1<=h, w<=105)의 바둑판으로 n(1<=n<=2000)의 칸이 있어 걸을 수 없습니다.(1,1)부터 (h,w)까지 몇 개의 경로(109+7에 대한 필름 추출)를 구합니다.
말 막고 강졸 막고 dp로 할 줄 알았어.데이터 범위를 주의하세요!이 문제가 어려운 이유는 데이터가 커서 dp(O(h∗w)로 무한TLE(시간 상한선은 2s)를 만들 수 있기 때문이다.
그리고 난 단호하게 포기했어...(ACM제는 속일 수 없으니까)/(예를 들어 o예)/~그리고 대신들의 문제풀이를 보고 만들었어.
보집 사상을 채택하다.dp[i]로 하여금 합법적으로 i번째 점까지 가는 경로수를 표시하게 하다.그러면 총 경로수(합법성을 따지지 않음)는 Cx-3-1x+y-3이다. 합법성이 아니면 걸을 수 없는 칸을 통과한다. 이런 경로는 ∑dp[j]가 있다.
조합수를 계산할 때, 현재 곱하기와 역원을 미리 처리합니다.역원을 계산하는 방법은 매우 많은데 여기서 나는 페마소정리ap-1≡1(modp)을 사용하는데 그 중에서 p는 소수이다.
이렇게 보면 이 문제는 그리 어렵지 않은데, 나는 포기했다......蒟蒻 화이팅↖(^ω^)↗
부코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long int
#define MAXN 2050
#define MAXM 200050
#define mod 1000000007
using namespace std;

int h ,w ,n ;
LL dp[MAXN] ,fact[MAXM] ,ni[MAXM] ;

struct node
{
    int x ,y ;
    bool operator < (const node &a) const
    {
        return x+y<a.x+a.y;
    }
}point[MAXN] ;

LL power(LL a,LL pos)
{
    LL ans=1;
    while(pos>0)
    {
        if(pos&1)
            ans=ans*a%mod;
        a=a*a%mod;
        pos>>=1;
    }
    return ans;
}

void init()
{
    fact[0]=ni[0]=fact[1]=ni[1]=1;
    for(int i=2;i<=200000;++i)
    {
        fact[i]=fact[i-1]*i%mod;
        ni[i]=power(fact[i],mod-2);
    }
}

LL C(int a,int b)
{
    return fact[a]*ni[b]%mod*ni[a-b]%mod;
}

int main()
{
    init();
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&point[i].x,&point[i].y);
            --point[i].x ,--point[i].y;
        }
        point[n].x=h-1 ,point[n].y=w-1 ;
        sort(point,point+n+1);
        int x=point[0].x ,y=point[0].y ,u ,v ;
        dp[0]=C(x+y,x);
        for(int i=1;i<=n;++i)
        {
            x=point[i].x ,y=point[i].y ;
            dp[i]=C(x+y,x);
            for(int j=0;j<i;++j)
            {
                u=point[j].x ,v=point[j].y ;
                if(v>y||u>x)continue;
                dp[i]=(dp[i]-dp[j]*C(x+y-u-v,x-u)%mod)%mod;
                if(dp[i]<0)dp[i]+=mod;
            }
        }
        printf("%I64d
",dp[n]);
    }
    return 0;
}