计数专题

发表于 更新于 分类于 阅读次数： Changyan：

计数问题一直是让我头疼的问题啊…最近开始整理相关的问题。

NamoCamp每日一题

#467. 路径计数2

有一个 n∗n 的网格，有些格子是可以通行的，还有 m 个格子是障碍。

一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案。

由于答案很大，输出对 1e9+7取模的结果。

输入格式

第一行两个数字 n, m。

接下来 m 行，每行 2 个整数 xi,yi，代表第 i 个障碍的坐标。

输出格式

一个数，表示答案。

样例输入

1
2
2 1
2 1

样例输出

1
1

数据规模

所有数据保证 1≤n≤106,1≤m≤3000,1≤xi,yi≤n

首先我们观察到数据范围不适合做n*n的DP，因此我们寻找突破口m=3000，设状态DP[i]表示从(1,1)到第i个障碍，其中不经过其他任何障碍的方案数.因此对于第i个障碍的转移需要其他所有状态中横纵坐标都小于第i个障碍的点来进行转移。

我们可以用BFS或者记忆化搜索来完成状态的转移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N=6010,M=2000010,mod=1e9+7;
pair<int,int> pos[N];
int f[N],fact[M],inv[M],n,m;//C[N][N];
int C(int n,int m){
	if(n<m) return 0;
	else if(n==m||m==0) return 1;
	return (LL)fact[n]*inv[n-m]%mod*inv[m]%mod;
}
void init(){
	fact[0]=1;
	rep(i,1,M-10) fact[i]=(LL)fact[i-1]*i%mod;
	inv[M-10]=fpower(fact[M-10], mod-2,mod);
	per(i,M-11,1) inv[i]=(LL)inv[i+1]*(i+1)%mod;
	inv[0]=1;
}
int dfs(int u){
	if(f[u]!=-1) return f[u];
	int res=0;
	for(int i=1;i<=m;++i){
		if(pos[i].x<=pos[u].x&&pos[i].y<=pos[u].y&&i!=u)
			res=(res+(LL)dfs(i)*C(pos[u].x-pos[i].x+pos[u].y-pos[i].y,pos[u].x-pos[i].x)%mod)%mod;
	}
	res=(((LL)C(pos[u].x-1+pos[u].y-1,pos[u].x-1)-res)%mod+mod)%mod;
	return f[u]=res;
}

void solve(){
	n=read(),m=read();
	rep(i,1,m) pos[i].x=read(),pos[i].y=read();
	pos[++m].x=n,pos[m].y=n;
	memset(f,-1,sizeof f);
	print(dfs(m));
}