题目大意,
5-> 5,1+4,2+3
6-> 6,1+5,2+4,1+2+3
求n的个数。
wa在了奇怪的地方………………没有啦,,跟学长对了思路是没错的,但是好像取模的时候有点问题……不知道怎么改。先说下思路。
要求每个数字的不同组合,设一个数组f[i][j]表示对于数i,包含从1-j的组合个数有多少个。然后经过观察可以发现,对于数i,f[i][j]=f[i-j][i-j]-f[i-j][j]+f[i][j-1]。
然后对与剩下的数,直接把值传递下去就好了。表示在学长的大思路下可以自己想出来怎么做还是很开心的。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define maxn 2010 #define ll __int64 //int mod=100999; int f[maxn][maxn]; int main() { int i,j,k; int mod=100999; //memset(f,0,sizeof(f)); f[1][1]=1; f[2][1]=0;f[2][2]=1; f[3][1]=1;f[3][2]=1;f[3][3]=2; for(i=4;i<maxn;i++) { if(i%2==0) k=i/2-1; else k=i/2; f[i][0]=0; for(j=1;j<=k;j++) { f[i][j]=((f[i-j][i-j]-f[i-j][j])+f[i][j-1])%mod; // if(f[i][j]>=mod) f[i][j]%=mod; // printf("f[%d][%d]=%I64d\n",i,j,f[i][ j]); } for(j=k+1;j<i;j++) f[i][j]=f[i][j-1];//printf("f[%d][%d]=%d\n",i,j,f[i][j]); f[i][i]=f[i][i-1]%mod+1; // if(f[i][i]>=mod) f[i][j]%=mod; // printf("%d %d\n",i,f[i][i]);//system("pause"); } int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%d\n",f[n][n]); } return 0; }