Submission #172292


Source Code Expand

Copy
#include <cstdio>

using namespace std;

long long mod = 1000000007;
int a[2222];

long long calc(long long p)
{
  return (p*(p+1)/2)%mod;
}

long long mod_pow(long long a,long long b,long long mod)
{
  if( b == 0 ) return 1;
  long long res = mod_pow(a*a%mod,b/2,mod);
  if( b&1 ) res = (res*a)%mod;
  return res;
}

long long inv(long long a,long long mod)
{
  return mod_pow(a,mod-2,mod);
}

long long C(long long n,long long r,long long mod)
{
  long long ret = 1;
  for(;;) {
    if( r == 0 ) break;
    long long N = n%mod;
    long long R = r%mod;
    if( N < R ) return 0;
    for( int i = 0; i < R; i++ ) {
      ret = ret*(N-i)%mod;
    }
    long long imul = 1;
    for( int i = 0; i < R; i++ ) {
      imul = imul * (i+1)%mod;
    }
    ret = ret*inv(imul,mod)%mod;
    n /= mod;
    r /= mod;
  }
  return ret;
}

int main(void)
{
  int n;
  long long res = 0;
  bool t = false;
  scanf("%d",&n);
  for( int i = 0; i < n; i++ ) {
    scanf("%d",a+i);
    t |= (a[i] < 0);
  }
  /*
  int c = 0, d = 0;
  for( int i = 2; i <= 9; i++ ) {
    //c += 9-i+1;
    d = 0;
    for( int j = i; j <= 9; j++ ) {
      //for( int k = j; k <= 9; k++ ) {
      //for( int ka = k; ka <= 9; ka++ ) {
          c += 1;
          //  }
          //}
      //printf("%d %d\n",i,j);
    }
    printf("%d\n",c);
    //c += d;
  }
  printf("%d\n",c);
  */
  res = 1;
  for( int i = 1; i < n-1; i++ ) {
    if( a[i] == -1 ) {
      int j = i;
      long long s = 0;
      while( a[j] == -1 ) ++j;
      //printf("%lld %d %lld\n",a[j]-a[i-1]+1,j-i, C(a[j]-a[i-1]+1,j-i,mod));
      //for( int k = 0; k <= a[j]-a[i-1]; k++ ) {
        //printf("%d %d %lld\n",a[j]-a[i-1]-(k-1),j-i-1,C(a[j]-a[i-1]-(k-1),j-i-1,mod));
      //s = (s+C(a[j]-a[i-1]-(k-1),j-i-1,mod))%mod;
      //}
      long long x = (a[j]-a[i-1])+(j-i);
      long long r = j-i;
      //printf("%lld %lld\n",x,r);
      //s = (((x-r)*C(x,r,mod)+r+1))%mod*inv(r+1,mod);
      s = C(x,r,mod);
      //printf("%lld\n",s);
      //s = C(a[j]-a[i-1]+1,j-i,mod);
      i = j-1;
      res = (res*s)%mod;
    }
  }
  printf("%lld\n",res);
  return 0;
}

Submission Info

Submission Time
Task C - タコヤ木
User roxion1377
Language C++ (G++ 4.6.4)
Score 100
Code Size 2197 Byte
Status AC
Exec Time 26 ms
Memory 904 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:53:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:55:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 23 ms 820 KB
sample_02.txt AC 24 ms 828 KB
sample_03.txt AC 24 ms 780 KB
subtask1_01.txt AC 23 ms 768 KB
subtask1_02.txt AC 23 ms 776 KB
subtask1_03.txt AC 21 ms 816 KB
subtask1_04.txt AC 20 ms 820 KB
subtask1_05.txt AC 21 ms 816 KB
subtask1_06.txt AC 26 ms 792 KB
subtask1_07.txt AC 23 ms 780 KB
subtask1_08.txt AC 21 ms 820 KB
subtask1_09.txt AC 23 ms 828 KB
subtask1_10.txt AC 24 ms 824 KB
subtask1_11.txt AC 22 ms 816 KB
subtask1_12.txt AC 25 ms 768 KB
subtask2_01.txt AC 23 ms 820 KB
subtask2_02.txt AC 22 ms 820 KB
subtask2_03.txt AC 21 ms 824 KB
subtask2_04.txt AC 22 ms 820 KB
subtask2_05.txt AC 21 ms 836 KB
subtask2_06.txt AC 22 ms 828 KB
subtask2_07.txt AC 22 ms 820 KB
subtask2_08.txt AC 22 ms 820 KB
subtask2_09.txt AC 26 ms 772 KB
subtask2_10.txt AC 21 ms 904 KB
subtask2_11.txt AC 22 ms 816 KB
subtask2_12.txt AC 22 ms 812 KB
subtask3_01.txt AC 20 ms 824 KB
subtask3_02.txt AC 19 ms 828 KB
subtask3_03.txt AC 20 ms 820 KB
subtask3_04.txt AC 22 ms 816 KB
subtask3_05.txt AC 21 ms 812 KB
subtask3_06.txt AC 21 ms 804 KB
subtask3_07.txt AC 25 ms 820 KB
subtask3_08.txt AC 23 ms 824 KB
subtask3_09.txt AC 24 ms 820 KB
subtask3_10.txt AC 25 ms 820 KB
subtask3_11.txt AC 23 ms 808 KB
subtask3_12.txt AC 24 ms 816 KB