Submission #20017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20017	2016-02-25T08:38:20 Z	xdoju	카드 (kriii4_Z)	C++14	0 / 100	1000 ms	71884 KB

Z

#include <stdio.h>

const int MOD = 1000000007;

int mul(int x, int y){ return (long long)x * y % MOD; }

int power(int x, int y){
  if(y == 0) return 1;
  int r = power(x, y / 2);
  r = mul(r, r);
  if(y % 2 == 1) r = mul(r, x);
  return r;
}

int modinv(int x){ return power(x, MOD - 2); }

int dp[3010][3010];
int comb[3010][3010];
int D[3010];
int maxL[3010];

int main(){
  int N, L; scanf("%d%d", &N, &L);
  for(int i = 1; i <= N; i++) scanf("%d", &D[i]);

  comb[0][0] = 1;
  for(int i = 1; i <= L; i++){
    comb[i][0] = 1;
    for(int j = 1; j <= i; j++){
      comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }
  }

  maxL[N] = L;
  for(int i = N - 1; i >= 0; i--) maxL[i] = maxL[i + 1] - D[i];

  dp[0][0] = 1;

  int zeroc = 0;

  for(int i = 1; i <= N; i++){
    if(D[i] == 0){
      zeroc++;
      for(int j = 0; j <= L; j++) dp[i][j] = dp[i - 1][j];
    }
    else{
      for(int j = 0; j <= maxL[i]; j++){
        for(int k = D[i]; k <= j; k++){
          dp[i][j] += mul(dp[i - 1][j - k], comb[j][k]);
          dp[i][j] %= MOD;
        }
      }
    }
  }

  int ans = 0;
  int moth = power(N, L);

  for(int i = 0; i <= L; i++){
    ans += mul(mul(dp[N][i], power(zeroc, L - i)), comb[L][i]);
    ans %= MOD;
  }

  printf("%d\n", mul(ans, modinv(moth)));
  return 0;
}

Subtask #1

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	71884 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-