Submission #172160


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std; using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
using SS = stringstream;
using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;
template < typename T = int > using LIM = numeric_limits<T>;

template < typename T > inline T fromString( const string &s ){ T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define AALL( a, t ) (t*)a, (t*)a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

constexpr int MOD = 1000000007;

// x^n を mod で求める
// 反復二乗法
long long mod_pow( long long x, long long n, long long mod )
{
	long long res = 1;
	while ( n )
	{
		if ( n & 1 )
		{
			( res *= x ) %= mod;
		}
		( x *= x ) %= mod;
		n >>= 1;
	}
	return res;
}

// p が素数のとき、mod p での逆元を求める
// フェルマーの小定理を利用
// incluide : mod_pow
int mod_inverse( long long a, long long p )
{
	return mod_pow( a, p - 2, p );
}

// 素数である mod の剰余系で n! を求める
class modFact
{
private:
	const int MAX_N, MOD;
	vector<int> fact;

public:
	modFact( const int n, const int mod ) : MAX_N( n ), MOD( mod ), fact( min( MAX_N + 1, MOD ) )
	{
		fact[0] = 1;
		for ( int i = 1; i < (int)fact.size(); ++i )
		{
			fact[i] = 1LL * fact[ i - 1 ] * i % MOD;
		}
		return;
	}

	int operator()( const int n )
	{
		int e;
		return operator()( n, e );
	}

	int operator()( const int n, int &e )
	{
		e = 0;
		if ( n == 0 )
		{
			return 1;
		}

		const long long res = operator()( n / MOD, e );
		e += n / MOD;

		if ( n / MOD % 2 != 0 )
		{
			return res * ( MOD - fact[ n % MOD ] ) % MOD;
		}
		return res * fact[ n % MOD ] % MOD;
	}
};
// modfact( max_n, mod )
// ()( n )
// ()( n, e )

// nCr
// include : modFact, mod_inverse
class modComb
{
private:
	const int MOD;
	modFact mod_fact;

public:
	modComb( const int n, const int mod ) : MOD( mod ), mod_fact( n, mod ) {};

	int operator()( const int n, const int r )
	{
		if ( n < 0 || r < 0 || n < r )
		{
			return 0;
		}

		int e1, e2, e3;
		long long a1 = mod_fact( n, e1 ), a2 = mod_fact( r, e2 ), a3 = mod_fact( n - r, e3 );
		if ( e1 > e2 + e3 )
		{
			return 0;
		}
		return a1 * mod_inverse( a2 * a3 % MOD, MOD ) % MOD;
	}
};
// modComb( n, mod )
// ()( n, r )

LL solve( const int N, const int M )
{
	VT<LL> dp( M + 1 );
	dp[0] = 1;

	REP( i, 0, M + 1 )
	{
		REP( j, 1, M - i )
		{
			( dp[ i + j ] += dp[i] * N ) %= MOD;
		}
	}

	return dp.back();
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	if ( 2000 < *max_element( ALL( as ) ) )
	{
		return 1;
	}

	VI ps;
	REP( i, 0, n )
	{
		if ( as[i] != -1 )
		{
			ps.PB( i );
		}
	}

	LL res = 1;

	REP( i, 0, ps.size() - 1 )
	{
		if ( ps[i] == ps[ i + 1 ] )
		{
			continue;
		}

		const int m = ps[ i + 1 ] - ps[i] - 1;
		const int d = as[ ps[ i + 1 ] ] - as[ ps[i] ] + 1;

		LL tmp = 0;

		REP( j, 1, m + 1 )
		{
			( tmp += modComb( d, MOD )( d, j ) ) %= MOD;
		}

		( res *= tmp ) %= MOD;
	}

	cout << res << endl;

	return 0;
}

Submission Info

Submission Time
Task C - タコヤ木
User torus711
Language C++11 (GCC 4.8.1)
Score 0
Code Size 4275 Byte
Status WA
Exec Time 119 ms
Memory 956 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 50 0 / 30 0 / 20
Status
AC × 2
RE × 1
AC × 2
WA × 12
AC × 3
WA × 23
AC × 1
WA × 23
RE × 12
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 64 ms 796 KB
sample_02.txt AC 23 ms 916 KB
sample_03.txt RE 26 ms 836 KB
subtask1_01.txt WA 25 ms 920 KB
subtask1_02.txt WA 25 ms 884 KB
subtask1_03.txt WA 23 ms 908 KB
subtask1_04.txt WA 25 ms 892 KB
subtask1_05.txt WA 24 ms 868 KB
subtask1_06.txt WA 25 ms 928 KB
subtask1_07.txt WA 22 ms 920 KB
subtask1_08.txt WA 22 ms 912 KB
subtask1_09.txt WA 26 ms 900 KB
subtask1_10.txt WA 22 ms 920 KB
subtask1_11.txt WA 25 ms 904 KB
subtask1_12.txt WA 25 ms 852 KB
subtask2_01.txt WA 23 ms 920 KB
subtask2_02.txt AC 23 ms 844 KB
subtask2_03.txt WA 26 ms 888 KB
subtask2_04.txt WA 25 ms 896 KB
subtask2_05.txt WA 23 ms 924 KB
subtask2_06.txt WA 22 ms 920 KB
subtask2_07.txt WA 119 ms 956 KB
subtask2_08.txt WA 21 ms 916 KB
subtask2_09.txt WA 26 ms 876 KB
subtask2_10.txt WA 27 ms 888 KB
subtask2_11.txt WA 23 ms 788 KB
subtask2_12.txt WA 24 ms 880 KB
subtask3_01.txt RE 20 ms 916 KB
subtask3_02.txt RE 28 ms 804 KB
subtask3_03.txt RE 21 ms 916 KB
subtask3_04.txt RE 25 ms 892 KB
subtask3_05.txt RE 23 ms 932 KB
subtask3_06.txt RE 25 ms 900 KB
subtask3_07.txt RE 26 ms 800 KB
subtask3_08.txt RE 24 ms 908 KB
subtask3_09.txt RE 20 ms 920 KB
subtask3_10.txt RE 22 ms 924 KB
subtask3_11.txt RE 86 ms 796 KB
subtask3_12.txt RE 24 ms 948 KB