2 条题解

  • 0
    @ 2025-10-8 16:56:46
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<cmath>
    using namespace std;
    #define x first
    #define y second
    const int SIZE = 2010;
    pair<int, int> a[SIZE];
    int h, w, n, f[SIZE], mod = 1000000007;
    long long jc[200010], jcinv[200010];
    
    int C(int n, int m) {
    	return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
    }
    
    long long power(long long a, int b) {
    	long long c = 1;
    	for (; b; b >>= 1) {
    		if (b & 1) c = c*a%mod;
    		a = a*a%mod;
    	}
    	return c;
    }
    
    int main() {
    	jc[0] = 1, jcinv[0] = 1;
    	for (int i = 1; i <= 200000; i++) {
    		jc[i] = jc[i - 1] * i % mod;
    		jcinv[i] = power(jc[i], mod - 2);
    	}
    	cin >> h >> w >> n;
    	for (int i = 1; i <= n; i++)
    		scanf("%d%d", &a[i].x, &a[i].y);
    	sort(a + 1, a + n + 1);
    	a[n + 1].x = h, a[n + 1].y = w;
    	for (int i = 1; i <= n + 1; i++) {
    		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
    		for (int j = 1; j < i; j++) {
    			if (a[j].x > a[i].x || a[j].y > a[i].y) continue;
    			f[i] = (f[i] - (long long)f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x)) % mod;
    		}
    	}
    	cout << (f[n + 1] + mod) % mod << endl;
    }
    
    • 0
      @ 2025-10-8 16:56:36
      #include<iostream>
      #include<cstdio>
      #include<cstring>
      #include<algorithm>
      #include<set>
      #include<queue>
      #include<cmath>
      using namespace std;
      #define x first
      #define y second
      const int SIZE = 2010;
      pair<int, int> a[SIZE];
      int h, w, n, f[SIZE], mod = 1000000007;
      long long jc[200010], jcinv[200010];
      
      int C(int n, int m) {
      	return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
      }
      
      long long power(long long a, int b) {
      	long long c = 1;
      	for (; b; b >>= 1) {
      		if (b & 1) c = c*a%mod;
      		a = a*a%mod;
      	}
      	return c;
      }
      
      int main() {
      	jc[0] = 1, jcinv[0] = 1;
      	for (int i = 1; i <= 200000; i++) {
      		jc[i] = jc[i - 1] * i % mod;
      		jcinv[i] = power(jc[i], mod - 2);
      	}
      	cin >> h >> w >> n;
      	for (int i = 1; i <= n; i++)
      		scanf("%d%d", &a[i].x, &a[i].y);
      	sort(a + 1, a + n + 1);
      	a[n + 1].x = h, a[n + 1].y = w;
      	for (int i = 1; i <= n + 1; i++) {
      		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
      		for (int j = 1; j < i; j++) {
      			if (a[j].x > a[i].x || a[j].y > a[i].y) continue;
      			f[i] = (f[i] - (long long)f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x)) % mod;
      		}
      	}
      	cout << (f[n + 1] + mod) % mod << endl;
      }
      • 1

      0x50 动态规划(0x5C 计数类DP)例题1:杰拉尔德和巨型象棋

      信息

      ID
      1393
      时间
      1000ms
      内存
      64MiB
      难度
      4
      标签
      递交数
      37
      已通过
      18
      上传者