吴旭华 发表于 2025-4-10 05:28:15

蓝桥杯OJ240 排列数

MOD=123456
n,k=map(int,input().split())#求k-1个折点
dp=[[*(k) for i in range(3) ]for j in range(n+1)]
dp=1
dp=2
dp=dp=2
dp=2
for i in range(4,n+1):
    for j in range(3):
      for t in range(0,min(k,i)):
            dp+=dp*(t+1)
            if t>=2:
                dp+=dp*(i-t-1)#注意不是*(i-t-3)
            if t>=1:
                if j==0 or j==2:       dp+=dp
                if j==1:               dp+=2*dp+2*dp
            dp%=MOD
print((dp+dp+dp)%MOD) 构建一个dp数组，dp i代表一共i个数来排列。j代表3个状态。k代表k个折点。(代码中用dp表示，并没有什么意思，只是符号不敷用了。。。）
现在来分析三个状态：
j==0 代表wwwww的外形的序列，两端都是较大值
j==1 代表NNNNNNNNNNN的外形的序列，两端分别是较大值和较小值
j==2 代表mmmmmmmmmm的外形的序列，两端都是较小值
 如图所示：https://i-blog.csdnimg.cn/direct/ba9f95ce1e934161bf7d1c08ef42001d.bmp
 然后分别讨论dp的递推关系https://i-blog.csdnimg.cn/direct/3b89b3157383468c95c6a6a4362de406.jpeg
前面的红笔写的是递推时要乘上的系数
然后再整理一下就能得到代码中的递推公式了~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: 蓝桥杯OJ240 排列数