题意:链接方法:数的划分解析:我终于A了这道题了！！百年老坑！！！！！！首先我承认这个玩意暴力我都不会写。或者暴力复杂度爆炸。
看上面这个图，这是个7*7的矩阵显然他可以由2,2,3来表示(RT);但是这里它划分出来的三个矩阵的表示方法必须是独有的。什么是独有的呢？以边长为4的矩阵演示一下。显然有两种填充方案。如下图。
但是第一种填充方案显然是由两个边长为2的矩阵构成的，不是他独有的方案。第二种填充方案便是它独有的填充方案，因为在这种填充方案中。找不到一个大小为i(i因为如果可以找到一个大小为i(i现在我们的目的就是求大小为n的矩阵的独有方案的个数。经过漫长的画图过程=-=发现只有如下的方案为独有的方案，并且长度为n的矩阵(n>=2)只有一个独有方案。
至于证明….（大胆猜想！小心假设！从不证明！于是这题就变水了，，既然任意长度n的矩阵(n>=2)都只有一个独有方案。所以这道题就变成了求将n划分成一堆大于等于2的数的方案数+1(这个1是它的独有方案)。直接O(n^2)预处理划分方案数即可。另外，惯性坑！取余数是1e8+7不是1e9+7！！！！！！！！代码:;ll;int t,n;int f[2010][2010];void init(){f[0][0]=1;for(int i=1;i<=2000;i++){for(int j=1;j<=i;j++){if(f[i-j][j])f[i][j]=(f[i-1][j-1]+f[i-j][j])%MOD;else f[i][j]=f[i-1][j-1];}}}int main(){init();scanf(“%d”,&t);while(t–){scanf(“%d”,&n);if(n==1){puts(“0”);continue;}if(n==2){puts(“1”);continue;}if(n==3){puts(“1”);continue;}int ans=0;for(int i=2;i<=n/2;i++){ans=(ans+f[n-i][i])%MOD;}printf(“%d\n”,ans+1);}}
有我们特有的记忆，亲情之忆友谊之花爱情之树以及遗憾之泪！
