#include

#include

#include

#include

#define INF 20091101

#define SIZE 100006

using namespace std; 

int dolls[100006],child[100006],befor[100006],save[100006],cache[100006]; 

vector a;

int waysToBuy(const vector &psum, int k) {

    const int MOD = 20091101;

    int ret = 0;

    //psum[]의 각 값을 몇 번이나 본 적 있는지 기록한다.

    vector count(k, 0);

    for (int i = 0; i

        count[psum[i]]++;

    //두 번 이상 본 적 있다면 이 값 중 두 개를 선택하는 방법의 수를 더한다.

    //순열과 조합 nC2 공식 적용

    for (int i = 0; i

        if (count[i] >= 2)

            ret = (ret + ((count[i] * (count[i] - 1)) / 2)) % MOD;

    return ret;

}

//D[]의 부분 합 배열 psum[]과 k가 주어질 때,겹치지 않게 몇 번이나 살 수 있는지 반환한다.

//psum[]의 첫 번째 원소 전에 0을 삽입했다고 가정한다.

int maxBuys(const vector& psum, int k) {

    //ret[i]=첫 번째 상자부터 i번째 상자까지 고려했을 때 살 수 있는 최대 횟수

    vector ret(psum.size(), 0);

    //prev[s]=psump[]이 s였던 마지막 위치

    vector prev(k, -1);

    for (int i = 0; i

        //i번째 상자를 아예 고려하지 않는 경우

        if (i > 0)

            ret[i] = ret[i - 1];

        else

            ret[i] = 0;

        //psum[i]를 전에도 본 적이 있으면,prev[psum[i]]+1부터 여기까지 쭉 사 본다.

        int loc = prev[psum[i]];

        if (loc != -1) ret[i] = max(ret[i], ret[loc] + 1);

        //prev[]에 현재 위치를 기록한다.

        prev[psum[i]] = i;

    }

    return ret.back();

}

  

void solve()

{

int n,k;

scanf("%d %d",&n,&k);

a.clear();

a.assign(n+1,0);

memset(dolls,0,sizeof(dolls));

memset(child,0,sizeof(child));

memset(befor,0,sizeof(befor));

memset(save,0,sizeof(save));

memset(cache,0,sizeof(cache));

child[0]++; 

for(int i=1; i<=n; i++)

{

scanf("%d",&dolls[i]);

dolls[i]=(dolls[i]+dolls[i-1])%k;

a[i]=dolls[i];

child[dolls[i]]++;

if(child[dolls[i]]==1)befor[i]=-1; 

else befor[i]=save[dolls[i]]; 

save[dolls[i]]=i; 

}

int sum=0; 

for(int i=0; i

{

if(child[i]>=2)sum=(sum+(child[i])*(child[i]-1)/2)%INF; 

}

printf("%d ",sum);

for(int i=1; i<=n; i++)

{

if(befor[i]!=-1)

{

cache[i]=max(cache[i-1],cache[befor[i]]+1); 

}

}

printf("%d\n",cache[n]);

}

int main()

{

freopen("input.txt","r",stdin);

int T;

scanf("%d",&T);

for(int i=0; i

}

이건데 내소스랑 종만이 소스랑 뭐가 다른지 분석해줄 수 있냐 solve밑에게 내소스고 저 재귀 함수 돌리는게 종만 소스임 

ㅅ발 뭐가 다른데 도대체 싸울까 진짜