有偿求助一道 离散数学的问题 100

子串，有顺序吧<br><br>【 在 IWhisper#322 (null) 的大作中提到: 】<br><font class="f006">: 想不明白f10为啥是奇数，不应该是两边对称的吗 </font>

微信还是QQ啊<br>【 在 IWhisper#442 的大作中提到: 】<br><font class="f006">: 这应该是个递推式？可以看看，只要有帮助，哪怕不是全部解出来了，也有红包 </font>

你python脚本确定对吗，product是算笛卡尔积的不是不放回全排列的<br><br>我算出来f10=38329398

什么意思，这个不应该是，全部位置都是a也可以吧？<br><br>【 在 IWhisper#213 (null) 的大作中提到: 】<br><font class="f006">: 你python脚本确定对吗，product是算笛卡尔积的不是不放回全排列的 </font><br><font class="f006">: 我算出来f10=38329398 </font>

微信<br><br>【 在 IWhisper#601 (null) 的大作中提到: 】<br><font class="f006">: 微信还是QQ啊 </font>

计算过程：9^7×8+9^4×10+9×4<br>【 在 IWhisper#213 的大作中提到: 】<br><font class="f006">: 你python脚本确定对吗，product是算笛卡尔积的不是不放回全排列的 </font><br><font class="f006">: 我算出来f10=38329398 </font><br><font class="f006">: ............ </font>

product函数貌似跑不出你说的这个意思，得用combinations之类的<br>【 在 IWhisper#442 的大作中提到: 】<br><font class="f006">: 什么意思，这个不应该是，全部位置都是a也可以吧？ </font>

要还没人解出来你说一声我加你吧<br>【 在 IWhisper#213 的大作中提到: 】<br><font class="f006">: product函数貌似跑不出你说的这个意思，得用combinations之类的 </font>

容斥定理，先算包含一个的，减去包含两个abc的，再加上包含三个abc的，比如f10的解法<br>包含一次：8*9^7<br>包含两次：15*9^4<br>包含三次：4*9<br>38263752 - 98415 + 36 就是n等于10的答案<br><br>更通用的情形的难点显然在于k个abc的位置的方案数，上面n等于10是我手摸出来的。不要求o1的话，n个位置塞k个abc<br>n = int(input())<br>k = int(input())<br><br>dp = [ [ 0 for _ in range(k+1) ] for _ in range(n+1) ]<br><br>dp[0][0] = 1<br>for i in range(1, n+1):<br><span class="emoji" style="font-size: 16px">&nbsp;</span> <span class="emoji" style="font-size: 16px">&nbsp;</span> dp[i][0] = 1<br><br>for i in range(3, n+1):<br><span class="emoji" style="font-size: 16px">&nbsp;</span> <span class="emoji" style="font-size: 16px">&nbsp;</span> for j in range(1, k+1):<br><span class="emoji" style="font-size: 16px">&nbsp;</span> <span class="emoji" style="font-size: 16px">&nbsp;</span> <span class="emoji" style="font-size: 16px">&nbsp;</span> <span class="emoji" style="font-size: 16px">&nbsp;</span> dp[i][j] = dp[i-1][j] + dp[i-3][j-1]<br><br>print(dp[n][k])<br>验证了n等于10是对的，想来应该没有大问题<br>【 在 IWhisper#442 的大作中提到: 】<br><font class="f006">: 一道组合数学的问题，求教？ </font><br><font class="f006">: 假设有9个字母, abcdefghi。 </font><br><font class="f006">: ............ </font>