Advertisement
Fshl0

Untitled

Jul 22nd, 2022
678
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxN = 1e3 + 9;
  6. const int maxM = 1e3 + 9;
  7. const int MOD = 1e9 + 7;
  8.  
  9. long long memo[maxN][maxM], N, M;
  10. long long nCr[maxN][maxN];
  11.  
  12. long long dp (int row, int lastRowOnes) {
  13.     if (row == N + 1)
  14.         return 1;
  15.    
  16.     if (memo[row][lastRowOnes] != -1)
  17.         return memo[row][lastRowOnes];
  18.    
  19.     long long res = 0;
  20.    
  21.     for (int powerOf2 = 2; powerOf2 <= 2 * M; powerOf2 *= 2) {
  22.         int thisRowSum = powerOf2 - lastRowOnes;
  23.        
  24.         if (thisRowSum <= M && thisRowSum >= 0) {
  25.             res += nCr[M][thisRowSum] * dp (row + 1, thisRowSum) % MOD;
  26.             res %= MOD;
  27.         }
  28.     }
  29.    
  30.     return memo[row][lastRowOnes] = res;
  31. }
  32.  
  33. int main() {
  34.     cin >> N >> M;
  35.    
  36.     nCr[0][0] = 1;
  37.     for (int i = 1; i <= M; i++) {
  38.         nCr[i][0] = nCr[i][i] = 1;
  39.        
  40.         for (int j = 1; j < i; j++) {
  41.             nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % MOD;
  42.         }
  43.     }
  44.    
  45.     memset (memo, -1, sizeof (memo));
  46.     long long res = 0;
  47.    
  48.     for (int i = 0; i <= M; i++) {
  49.         res += dp (2, i) * nCr[M][i] % MOD;
  50.         res %= MOD;
  51.     }
  52.    
  53.     cout << res << "\n";
  54.     return 0;
  55. }
  56.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement