PID85 / 三个袋子
题目描述

背景

平平在公园里游玩时捡到了很多小球,而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里(袋子可以为空)。他想知道他总共有多少种放法。

题目描述

将N个不同的球放到3个相同的袋子里,求放球的方案总数M。

结果可能很大,我们仅要求输出M mod K的结果。

现在,平平已经统计出了N<=10的所有情况。见下表:

N 1 2 3 4 5 6 7 8 9 10

M 1 2 5 14 41 122 365 1094 3281 9842

数据规模

对于 40%数据,10<=N<=10,000

对于100%数据,10<=N<=1,000,000,000

对于 100%数据,K<=100,000

输入格式

两个整数N,K,N表示球的个数。

输出格式

输出仅包括一行,一个整数M mod K 。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论