摘要
Title: 523. 组合数问题
Tag: 组合数、二位前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

523. 组合数问题

• 题意

  见原题

• 思路

  
  只能处理余数，不然会爆longlong

• 代码

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  
  
  
  #define int long long
  
  using namespace std;
  
  const int N = 2010;
  int c[N][N], s[N][N];
  int n, m, t, k;
  
  int cnt;
  signed main(){
      
      scanf("%lld%lld", &t, &k);
      
      
      for (int i = 0; i < N; i ++ )
          for (int j = 0; j <= i; j ++ )
          {
              if (!j) c[i][j] = 1 % k;
              else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
  
              if (!c[i][j]) cnt += 1, s[i][j] = 1;
          }
      for (int i = 0; i < N; ++ i ){
          for(int j = 0; j < N; ++ j){
              if (i) s[i][j] += s[i - 1][j];
              if (j) s[i][j] += s[i][j - 1];
              if (i && j) s[i][j] -= s[i - 1][j - 1];
          }
      }
      for (int i = 0; i < t; i ++ ){
          scanf("%lld%lld", &n, &m);
          printf("%lld\n", s[n][m]);
      }
  }