「会津大学オンラインジャッジ思考中問題一覧」の編集履歴(バックアップ)一覧に戻る
int size=n*n; int t,sum; std::map<int,int> memo[2002]; std::map<int,int>::iterator it;
s-=(size*(size+1))/2; if(s==0){ printf("1\n"); return ; } memo[0][0]=1;
int ans=0; for(int i=0;i<=size;i++){ t=size-i; for(int j=0;j<m;j++){ if(size+j>m) break; if(memo[j].empty()==true) break; if(i==size){ it=memo[j].lower_bound(s-1); }else{ it=memo[j].begin(); }
while(it!=memo[j].end()){ sum=(*it).first+t; if(i==size-1){ if((*it).first==s){ ans+=(*it).second; ans%=100000; break; } }
if(sum>s) break; if(memo[j+1].find(sum)==memo[j+1].end()){ memo[j+1][sum]=memo[j][(*it).first]; }else{ memo[j+1][sum]=(memo[j][(*it).first]+memo[j+1][sum])%100000; } it++; } } /* for(int k=0;k<m;k++){ it=memo[k].begin(); if(it==memo[k].end()) break; printf("\n%d\n",k); while(it!=memo[k].end()){ printf("<%d %d>",(*it).first,(*it).second ); it++; } } */ } printf("%d\n",ans);
int n,m,s; scanf("%d %d %d",&n,&m,&s); while(n!=0 || m!=0 || s!=0){ calc(n,m,s); scanf("%d %d %d",&n,&m,&s); }