AcWing 2409. 游戏中的学问
原题链接
困难
作者:
XianZS.py
,
2025-03-13 22:44:18
·陕西
,
所有人可见
,
阅读 2
import os
import sys
""" 前提条件 """
# 至少3个人组成一个队伍
""" 输入数据 """
n,k,p=map(int,input().split())
""" 创建存储数组 """
nums=[[0 for _ in range(n+1)]for _ in range(n+1)]
""" 初始化存储数组 """
# 存在3个人,组成一个圈,存在两种情况
nums[3][1]=2
""" 动态规划操作 """
for x in range(4,n+1):
for y in range(1,k+1):
# 插入当前的圈之中
# num1=nums[x-1][y]*(x-1)
# 新建一个圈,需要从之前的n-1个人抽出2个
# 抽出第一个人的可选择方案数为 n-1
# 抽出第二个人的可选择方案数为 n-2
# num2=nums[x-3][y-1]*(n-1)*(n-2)
nums[x][y]=(nums[x-1][y]*(x-1)+nums[x-3][y-1]*(x-1)*(x-2))%p
print(nums[n][k])