Submission #1443204

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;


int N, C, A[400], B[400];
int64 mat[401][401];

int main()
{

  cin >> N >> C;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < N; i++) cin >> B[i];

  for(int i = 0; i < N; i++) {
    for(int k = A[i]; k <= B[i]; k++) {
      int64 ret = 1;
      for(int j = 0; j <= C; j++) {
        (mat[i][j] += ret) %= mod;
        (ret = ret * k) %= mod;
      }
    }
  }

  vector< int64 > curr(C + 1, 0);
  curr[0] = 1;
  for(int i = 0; i < N; i++) {
    vector< int64 > next(C + 1, 0);
    for(int j = 0; j <= C; j++) {
      for(int k = 0; k <= j; k++) {
        (next[j] += curr[j - k] * mat[i][k]) %= mod;
      }
    }
    curr.swap(next);
  }

  cout << curr[C] << endl;
}

Submission Info

Judge Result