高校问答校园网检测到猎豹wifi:NOIP2004一道选择题<回答要求过程证明>
来源：百度文库 编辑：高校问答 时间：2024/05/10 15:25:07
由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。
A. 40320 B. 39600 C. 840 D. 780 E. 60
我知道选D。要求高手证明，思路清晰者赏分20
A. 40320 B. 39600 C. 840 D. 780 E. 60
我知道选D。要求高手证明，思路清晰者赏分20
您高二没？没有也没关系。搞OI的排列组合一定要学好的。本人小五就学了。
现用排列组合解之。
先求子串中含至少含一个abc的情况数：
3a 5b 2c 中扣去一个abc 后 剩下 2a 4b 1c
2a 4b 1c 组成的字符串有 （2+4+1）！/（2！*4！*1！）＝105 种
把abc插入其中，有 （2+4+1）+1＝8 种插法
总计为 105*8＝840 种
但这里面含有两个abc的情况也算在内了，并且每个含两个abc的子串都被多算了一次（可以理解吧）
所以要扣去多算的
含两个abc的情况数：
3a 5b 2c 中扣去2个abc 后 剩下 1a 3b
把2个abc当作两个元素，与1个a及3个b 排列组合
有 (2+1+3)!/(2!*1!*3!)=60种
所以本题答案为 840-60＝780 种。