Path count 2 (DP + number of combinations)

daimayuan A daily topic div1 202

Solution

1. dp[i] Go to the first place i Number of legal solutions for obstacles
2. Come to the point （x, y） The number of all the schemes ：$C(x+y-2,x-1)$
3. $dp[i]=C(i.x+i.y-2,i.x-1)-\sum dp[j]\ast C(i.x-j.x+i.y-j.y,i.x-j.x)$
   namely ： Number of legal schemes = Number of all schemes - Number of all illegal schemes

Code

const ll mod = 1000000007;
using namespace std;
const int N = 2e6 + 5;

ll f[N];
ll inv[N], fac[N];
void init()
{
    
	fac[0] = inv[1] = inv[0] = 1;
	// Be careful ：inv[0] = 1,  That is, the inverse of the factorial of zero is 1
	for (int i = 1; i <= 2e6; i++)
		fac[i] = fac[i - 1] * i % mod;
	
	// Find out first 1~n Inverse element 
	for (int i = 2; i <= 2e6; i++)
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	//1~n The inverse element accumulation of is  1~n The inverse element of the factorial of 
	for (int i = 2; i <= 2e6; i++)
		inv[i] = inv[i] * inv[i - 1] % mod;
}

ll C(int n, int m)
{
    
	return fac[n] * inv[n - m] % mod * inv[m] % mod;
}

pii s[N];
int main()
{
    
	IOS;
	init();
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> s[i].ft >> s[i].sd;

	s[m + 1] = {
     n, n };
	for (int i = 1; i <= m + 1; i++)
	{
    
		f[i] = C(s[i].ft + s[i].sd - 2, s[i].ft - 1);
		for (int j = 1; j < i; j++)
		{
    
			ll t = C(s[i].ft - s[j].ft + s[i].sd - s[j].sd, s[i].ft - s[j].ft);
			f[i] = ((f[i] - f[j] * t % mod) % mod + mod) % mod;
		}
	}
	cout << f[m + 1] << endl;


	return 0;
}