【ch18】fff的诅咒

2015年4月3日1,3142

背景

06年的浙江考生还是很不服,于是我再水了一题。

描述

设A,B是两个非空集合,如果存在一法则f,使得对A中的每个元素按法则f在B中有唯一确定的元素与之对应,则称f为从A到B的映射,记作f:A→B,映射在数学及相关的领域经常等同于函数。

设s是由1到n的所有正整数组成集合,定义映射f:A→B。

已知n,求满足的映射f有多少个?

这个数可能很大,你只需要给出答案对质数p取模的值即可。

输入格式

三个空格隔开的正整数n,k,p。

输出格式

一个整数,表示答案对p取模的值。

样例输入

样例输出

数据范围与约定

  • 对于10%的数据:k\le1
  • 对于30%的数据:n,k\le25
  • 对于60%的数据:n\le100
  • 对于100%的数据:1\le n\le200,0\le k<2^{31},1<p\le10^6

样例解释

{f(1),f(2),f(3)}的可能分别是{1,1,1},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,3},{2,2,2},{2,2,3},{3,2,3},{3,3,3}。

来源

原创

题解
本质是求n个点,最大深度不超过k+1的森林数
f[i][j]表示森林有i个点,最大深度为j
s[i][j]表示森林有i个点,最大深度不超过j
因为还有标号问题所以要排列组合什么的。。。
转移方程意会一下T T

 

  • 黄学长的小号2015年4月3日 下午11:57 回复

    好一个意会一下

    #1  
  • stk2017年3月31日 下午5:00 回复

    %%%%%%%%%%%%%%,所以说k是什么…题面中貌似没有

    #2