多校杭电5794 大组合数（lucas）+dp

Problem Description

There is a

Input

The input consists of multiple test cases.
For each test case:
The first line is three integers,

Output

For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module

Sample Input

1 1 0

3 3 0

4 4 1

2 1

4 4 1

3 2

7 10 2

1 2

7 1

Sample Output

Case #1: 1

Case #2: 0

Case #3: 2

Case #4: 1

Case #5: 5

一个n*m的棋盘,一个棋子想从(1,1)走到(n,n)

棋子每步可从(x1,y1)到达(x2,y2),当且仅当

另外,棋盘上有r处障碍,棋子无法到达障碍处

问棋子从(1,1)到达(n,m)有多少种走法

【类型】
lucas定理求组合数+dp

【分析】
首先我们要确定棋子是怎么走的

由式子,x2>x1,y2>y1可知

方程有两组解,x2=x1+2,y2=y1+1或x2=x1+1,y2=y1+2

即当棋子处于位置(x,y)时,它可以一步到达①(x+1,y+2)或②(x+2,y+1)处

那我们不妨求解一下通式,假设从位置(x1,y1)到(x2,y2)需要①走法走k1步,②走法走k2步

那么可得方程组

求解得

然后,因为从(x1,y1)到(x2,y2)在无障碍的情况下与走法先后无关,只与k1,k2有关

所以从(x1,y1)到(x2,y2)的方法数为或

组合数?还是大组合数,显然,lucas派上用场了

那么,障碍怎么办?比赛的时候想到了容斥,但感觉若r个障碍都可达的话,容斥复杂度还是蛮高的,但是官方题解给的就是容斥

算了,我们还是管自己的方法来解,dp

令dp[i]表示到第i个障碍前面不经过任何障碍的方案数然后转移的时候算出(1,1)到第i个障碍的方案数枚举j从1到i-1所有的障碍,减去从(1,1)出发只经由障碍j再到障碍i的方案数最后将重点(n,m)作为第r+1个障碍
ans就是dp[r+1]
这样复杂度是O(r^2)的

【时间复杂度&&优化】
O(r^2)

 1 #include<algorithm>
 2 
 3 #include<iostream>
 4 #include<stdio.h>
 5 #include<map>
 6 #include<vector>
 7 #include<math.h>
 8 #include<string.h>
 9 using namespace std;
10 #define ll long long
11 #define mod 110119
12 #define INF 0x3f3f3f3f
13  #define  pai (sqrt(5)+ 1)/2
14 #define pi acos(-1.0)
15 ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} //最大公约数
16 ll lcm(ll a,ll b){return a/gcd(a,b)*b;}//最小公倍数
17 ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
18 //求平方数
19 double dpow(double a,ll b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
20 ll f[mod+10];
21 ll dp[102];
22 struct aa
23 {
24     ll x;
25     ll y;
26 }a[102];
27 bool cmp(aa t1,aa t2)
28 {
29     if(t1.x==t2.x)return t1.y<t2.y; //排序
30     return t1.x<t2.x;
31 }
32 void init()
33 {
34     f[0]=1;
35   for(int i=1;i<=mod;i++)//初始化阶乘
36         f[i]=(f[i-1]*i)%mod;
37 }
38 ll C(ll n,ll m)
39 {
40     if(n<m)return 0;
41     return f[n]*powmod(f[m]*f[n-m]%mod,mod-2,mod);//费马定理
42 }
43 ll  lucas(ll n,ll m)
44 {
45     if(m==0)return 1;
46     return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;//大组合数
47 }
48 bool  judge(int i,int j)
49 {
50     if(a[i].x<a[j].x||a[i].y<a[j].y)
51         return false;
52     return true;
53 }
54 ll cal(ll i,ll j)//是否可以从i到达j
55 {
56     ll t1=a[j].x-a[i].x,t2=a[j].y-a[i].y;
57     ll k1=2*t2-t1,k2=2*t1-t2;
58     if(k1<0||k2<0||k1%3||k2%3)
59         return 0;
60         k1/=3;
61         k2/=3;
62     return lucas(k1+k2,k1);
63 }
64 int main()
65 {
66     init();
67     int case1=1;
68     ll n,m,r;
69     while(~scanf("%lld %lld %lld",&n,&m,&r))
70     {
71         printf("Case #%d: ",case1++);
72     for(int i=1;i<=r;i++)
73          scanf("%lld %lld",&a[i].x,&a[i].y);
74          a[0].x=a[0].y=1;
75         a[r+1].x=n;
76         a[r+1].y=m;
77         sort(a+1,a+1+r,cmp);
78         for(int i=1;i<=r+1;i++)
79         {
80             dp[i]=cal(0,i);
81             for(int j=1;j<i;j++)
82                 if(judge(i,j))
83                  dp[i]=(dp[i]+mod-cal(j,i)*dp[j]%mod)%mod;
84         }
85         printf("%I64d
",dp[r+1]);
86     }
87     return 0;
88 }

View Code