//-1 번째를 계산해야 하므로 H[-1] 과 같은 효과를 주어 다른 것을 1칸씩 뒤로 미루고 0 에 0 을 넣는다.
//(A-B)%M 은 A%M - B%M 과 같다..?
#include <stdio.h>
#define N 4 //인형 상자의 수
#define K 1 //어린이 수
int present[100000]; //인형 상자
int partialSum[100000];
int cache[100000];
int count[100000];
//Max(0~n 까지의 선물배열의 연속 부분 집합 중 K 로 나눠지는 것의 개수)
int multipleMemoizationDP(int T){
if(T<=0){
// if(partialSum[T]==0){return 1;}
return 0;
}
//포함하지 않는 경우.
int & ret = cache[100000];
if(ret!=-1){return ret;}
int max1 = multipleMemoizationDP(T-1);
int h=T-1;
//포함하는 경우.
for(;h>=0;h--){
if(partialSum[h] == partialSum[T]){
break;
}
}
int max2=multipleMemoizationDP(h)+1;
ret = max1>max2 ? max1:max2;
return ret;
}
int multipleRepeatDP(int T){
int ret[100000];
int returnValue = 0;
int prev[K];
for(int i=0;i<100000;i++){
ret[i] = 0;
if(i<K){
prev[i]=-1;
}
}
//이번 것을 넣지 않거나, 같은 psum을 가진 것 중 가장 큰 것을 넣는다.
//ret[i]=max(ret[i-1], ret[prev[psum[i]]);
for(int i=0;i<T;i++){
if(i>0){
ret[i]=ret[i-1];
}
//처음 본 나머지가 아니라면 max 를 정하는 것에 둔다.
if(prev[partialSum[i]]!=-1){
ret[i] = (ret[prev[partialSum[i]]]+1)>ret[i]?(ret[prev[partialSum[i]]]+1):ret[i];
returnValue=ret[i];
}
prev[partialSum[i]] = i;
}
return returnValue;
}
//psum 의 나머지가 같으면 K로 반드시 나눠진다.
int main(){
for(int i=0;i<100000;i++){
cache[i]=-1;
}
int Answer1=0;
int i=0,Answer2=0;
int T=0,H=T;
present[0]=0;//1 //0
present[1]=1;//1 //1
present[2]=2;//3 //3
present[3]=3;//6 // 2
&nbs\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0p; present[4]=4;//10 // 2
present[5]=5;//15 // 3
present[6]=6;//21 // 1
present[0]=0;
present[1]=1;
present[2]=2;
present[3]=3;
present[4]=4;
partialSum[0] = 0;
for(i=1;i<=N+1;i++){
int psum=0;
for(int j=0;j<i;j++){
psum += present[j];
}
partialSum[i-1] = psum %K;
}
//문제 1 O(N^2)
//조합의 수를 구한다.
for(i=1;i<=N+1;i++){
count[partialSum[i-1]] ++;
}
//btt = Bigger than two (count 배열 중 2를 넘는 것)
//btt C 2
for(i=0;i<K;i++){
if(count[i]>=2){
Answer1 = (Answer1 + (count[i]*(count[i]-1)) /2)%20091101 ;
}
}
//문제 2 Max(0~n 까지의 선물배열의 연속 부분 집합 중 K 로 나눠지는 것의 개수)
Answer2 = multipleRepeatDP(N+1);
printf("%d %d
",Answer1,Answer2);
}
