Confusion-白红宇

Confusion

阅读量：5266 次

发布时间：2019-06-14

本文共 2666 字，大约阅读时间需要 8 分钟。

【题意说明】

有一个1～N这N个数构成的序列，若前面的数比其后面的数要大，则这两个数就构成了一个Confused对。现在给你数N，和Confused对C，问由N个构成的序列有多少种满足C个Confused对。由于所求的数可能太大，所以最后的结果取对1000000007求余的结果。

【问题分析】

这显然是一个数论中的统计数问题了。

一开始，我是这样思考的，设f[n][c]=0为所求的值：

假定前N-1个数构成的某个序列，现在要加入第N个数，考虑其所加入的位置：

(1)在最后一个位置，则有：f[n][c]+=f[n-1][c]

(2)在倒数第2个位置，由于N是最大的数，所以必然与最后一个数产生一个Confused对，这样则有：f[n][c]+=f[n-2][c-1]

(3)在倒数第3个位置，N与最后2个数产生2个Confused对，且最后两个数也可能产生1个Confused对，这样就有：f[n][c]+=f[n-3][c-2]+f[n-3][c-3] *f[2][1]

(3)在倒数第4个位置，N与最后3个数产生3个Confused对，且最后3个数也可能产生1、2、3个Confused对，这样就有：

f[n][c]+=f[n-4][c-3]+f[n-4][c-4]*f[3][1]+f[n-4][c-5]*f[3][2]+f[n-4][c-6]*f[3][3]

……

这样往下推，显然越到后面式子变得越来越复杂，而且上面的式子需要计算出f[n][c]，要通过三层循环来完成，即时间复杂度为o(n^2*c)，更要命的是没办法去消除一层循环，所以感到很绝望！！

不过，把N放在某个序列的每两个数之间的位置的想法一直让我觉得是条出路，没办法之下拿些数据画画，第1个发现是对称性（虽然这个在后面没多大用处，不过也让我看到了坚持的希望吧！）。

再接着，不知道哪个筋搭错了，突然想把前3个数的所有序列给列出了，然后又列出4个数的序列！！为了说明，就写出这样的序列吧！

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1 2 3 4

1 3 2 4

2 1 3 4

2 3 1 4

3 1 2 4

3 2 1 4

1 2 4 3

1 3 4 2

2 1 4 3

2 3 4 1

3 1 4 2

3 2 4 1

1 4 2 3

1 4 3 2

2 4 1 3

2 4 3 1

3 4 1 2

3 4 2 1

4 1 2 3

4 1 3 2

4 2 1 3

4 2 3 1

4 3 1 2

4 3 2 1

从上面所写的大家看到了什么？哦原来4个数的序列真是由3个数的序列把4插入在不同位置生成的啊！（好像是废话吧！不过我感觉好像是发现真理一样！）而且还发现一个重要的东西：若原来3个数序列的Confused对有x个，则把4放在最后，Confused对还是x个，把4放在倒数第2个位置，则Confused对为x+1（因为此时4与最后一个数产生一个Confused对），把4放在倒数第3个位置，则Confused对为x+2（因为此时4与最后2个数产生2个Confused对，其它的不变）！哦！！到这里我才发现这个重要的性质！！重新置表：

对于3个数，则有：

C数	0	1	2	3
个数	1	2	2	1

对于4个数呢？则有以下关系：

C数	0	1	2	3	4	5	6
4在最后	1	2	2	1
4在倒数第2		1	2	2	1
4在倒数第3			1	2	2	1
4在倒数第4				1	2	2	1
合计	1	3	5	6	5	3	1

显然对于5、6……N都可以用这种方法也推出，这里再列出5的情况表：

C数	0	1	2	3	4	5	6	7	8	9	10
5在最后	1	3	5	6	5	3	1
5在倒数第2		1	3	5	6	5	3	1
5在倒数第3			1	3	5	6	5	3	1
5在倒数第4				1	3	5	6	5	3	1
5在倒数第5					1	3	5	6	5	3	1
合计	1	4	9	15	20	22	20	15	9	4	1

可以看出若以这在方法，其了需要三重循环来完成计算，时间复杂度也是o(n^2*c)，好在这个方法还有其优化的机会！再来看其生成的规律了，令f[n][c]表示生成的数，令w=0，以5为例则有：

F[5][0]=f[4][0]	w+=f[4][0]	f[5][0]=w
f[5][1]=f[4][1]+f[4][0]	w+=f[4][1]	f[5][1]=w
f[5][2]=f[4][2]+f[4][1]+f[4][0]	w+=f[4][2]	f[5][2]=w
f[5][3]=f[4][3]+f[4][2]+f[4][1]+f[4][0]	w+=f[4][3]	f[5][3]=w
f[5][4]=f[4][4]+f[4][3]+f[4][2]+f[4][1]+f[4][0]	w+=f[4][4]	f[5][4]=w
f[5][5]=f[4][5]+f[4][4]+f[4][3]+f[4][2]+f[4][1]	w+=f[4][5]-f[4][0]	f[5][5]=w
f[5][6]=f[4][6]+f[4][5]+f[4][4]+f[4][3]+f[4][2]	w+=f[4][6]-f[4][1]	f[5][6]=w
f[5][7]=f[4][7]+f[4][6]+f[4][5]+f[4][4]+f[4][3]=f[4][6]+f[4][5]+f[4][4]+f[4][3]	w-=f[4][2]	f[5][7]=w
f[5][8]=f[4][8]+f[4][7]+f[4][6]+f[4][5]+f[4][4]=f[4][6]+f[4][5]+f[4][4]	w-=f[4][3]	f[5][8]=w
f[5][9]=f[4][9]f[4][8]+f[4][7]+f[4][6]+f[4][5]=f[4][6]+f[4][5]	w-=f[4][4]	f[5][9]=w
f[5][10]=f[4][10]+f[4][9]f[4][8]+f[4][7]+f[4][6]=f[4][6]	w-=f[4][5]	f[5][10]=w