CSES 1078 - Grid Paths 解題心得( 題目 )
解題概念:DP、數學(包含:排組、快速冪、模逆元)
解題方法:首先我們如果使用純DP，探討到達(i,j)的方法數dp[i][j]，雖然方法合理，但是複雜度O(n^2)很不妥。
由於題目m只給到1000，我們換從m下手，因為就算O(m^2)也還可。我們定義dp[i]代表走到i(假設i的座標為x,y)且不經其他障礙方法數，轉移式:dp[i]=C(x+y-2,y-1)- dp[b]*C(i-b)，其中b指的是在到達i之前可能可到達的障礙物、C為排組，為了避免重複計算，我們要把重複路徑刪除。
另外排組C可以透過快速冪、模逆元計算，這裡在計算結果之前已先預處理建表。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2021/01/30
import java.io.*;
import java.util.*;
public class cses1078 {
public static int r,ret;
public static final int p=(int)Math.pow(10,9)+7,ma=(int)Math.pow(10,6)*2+5;
public static long temp;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long[] fac=new long[ma];
public static long[] inv=new long[ma];
public static P[] pt;
public static void main(String[] args) throws Exception{
init();
final int n=readint();
final int m=readint();
pt=new P[m+1];
for(int i=0;i<m;i++) {
pt[i]=new P(readint(),readint());
}
pt[m]=new P(n,n);
Arrays.sort(pt,new Comparator<P>() {
public int compare(P f,P s) {
if(f.x==s.x)return f.y-s.y;
return f.x-s.x;
}
});
for(int i=0;i<=m;i++) {
pt[i].v=C(pt[i].x+pt[i].y-2,pt[i].y-1);
pt[i].v%=p;
for(int j=i-1;j>=0;j--) {
if(pt[i].y<pt[j].y)continue;
pt[i].v-=(pt[j].v*C(pt[i].y-pt[j].y+pt[i].x-pt[j].x,pt[i].y-pt[j].y));
if(pt[i].v<0) {
pt[i].v+=((-pt[i].v)/p+1)*p;
}
}
pt[i].v%=p;
}
System.out.println(pt[m].v);
}
public static void init() {
fac[0]=1;
for(int i=1;i<ma;i++)fac[i]=fac[i-1]*i%p;
for(int i=0;i<ma;i++)inv[i]=fast((int)fac[i],p-2);
}
public static long C(int n,int k) {
return (fac[n]*inv[k]%p)*inv[n-k]%p;
}
public static long fast(int x,int l) {
if(l==1)return x;
if(l%2==0) {
temp=fast(x,l/2);
return temp*temp%p;
}
else {
temp=fast(x,l/2);
return (temp*temp%p)*x%p;
}
}
public static int readint() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
class P{
int x,y;
long v;
P(int a,int b){
x=a;
y=b;
}
}
文章標籤
全站熱搜
