OMO수열(one and minus one) > 문제은행



문제은행

2602 : OMO수열(one and minus one)

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 20 회    시도횟수: 75 회   



아래와 같은 특성을 갖는 수열 A를 생각해 보자.
1) 수열의 원소의 개수는 n(1≤n≤10000)개이다.
2) 구성된 원소는 1 또는 -1이다.
3) 모든 원소의 합은 ≥0 이다.

 

이수열의 원소들의 위치를 서로 바꾸어 아래와 같은 특성을 모두 만족하는 수열을 만들고자 한다.
a1≥0
a1+a2≥0
a1+a2+a3≥0
...
a1+a2+a3+...+an≥0.

 

수열 A와 n 이 주어질 때 위와 같은 특성을 만족하는 수열을 모두 몇 가지나 만들 수 있는지 찾아내는 프로그램을 작성하시오. 가지 수가 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.




첫 행에 수열의 개수 n(1≤n≤10,000) 이 입력된다.
두 번째 행에 1과 -1 로 구성된 n개의 수열이 공백으로 구분하여 주어진다.



위 특성을 만족하는 수열의 가지 수를 1,000,000,007로 나눈 나머지를 출력한다.


4
1 1 -1 -1
2


6
1 -1 1 1 -1 -1
5


5
1 -1 -1 -1 1
0


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.