Submission #1217674

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define MOD 1000000007

int N, C;
int A[400], B[400];
int T[401][401];
int dp[401][401];
int pow[401][401];

int pow_mod(int x, int k) {
  int a = 1;
  while (k > 0) {
    if (k & 1LL) a = (1LL*a*x) % MOD;
    x = (1LL*x*x) % MOD;
    k >>= 1;
  }
  return a;
}

int g(int n, int c) {
  return (0LL + MOD + T[B[n]][c] - T[A[n]-1][c]) % MOD;
}

int f(int n, int c) {
  if (dp[n][c] != -1) return dp[n][c];
  if (n == N-1) return g(n, c);
  int s = 0;
  for (int i=0; i<=c; i++) {
    s += (1LL * g(n, i) * f(n+1, c-i)) % MOD;
    s %= MOD;
  }
  return dp[n][c] = s;
}

signed 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<=400; i++) {
    for (int j=0; j<=400; j++) {
      pow[i][j] = pow_mod(i, j);
    }
  }
  for (int i=1; i<=400; i++) {
    for (int j=0; j<=400; j++) {
      T[i][j] = (T[i-1][j] + pow[i][j]) % MOD;
    }
  }
  for (int i=0; i<=N; i++) {
    for (int j=0; j<=C; j++) {
      dp[i][j] = -1;
    }
  }
  cout << f(0, C) << "\n";
  return 0;
}

Submission Info

Judge Result