60pts dp大水题求助
查看原帖
60pts dp大水题求助
719978
DYYqwq楼主2023/1/17 16:30

这东西能寄两个测试点???

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , m;
const int mod = 100003;
int dp[1010][1010];
bool flag[1010][1010];
signed main()
{
	scanf("%lld%lld" , &n , &m);
	for(int i = 1 ; i <= m ; i ++)
	{
		int x , y;
		scanf("%lld%lld" , &x , &y);
		flag[x][y] = true;
	}
	for(int i = 1 ; i <= n ; i ++)
	{
		if(!flag[i][1]) dp[i][1] = 1;
		if(!flag[1][i]) dp[1][i] = 1;
	}
	for(int i = 2 ; i <= n ; i ++)
	{
		for(int j = 2 ; j <= n ; j ++)
		{
			if(!flag[i][j])
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
	/*
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 1 ; j <= n ; j ++)
			printf("%d " , dp[i][j]);
		printf("\n");
	}
	*/
	printf("%lld" , dp[n][n] % mod);
	return 0;
}
2023/1/17 16:30
加载中...