1697 ⑨要写信
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 琪露诺(冰之妖精)有操控冷气的能力。能瞬间冻结小东西,比普通的妖精更危险。一直在释放冷气的她周围总是非常寒冷。 由于以下三点原因…… 琪露诺的符卡 冰符“Icicle Fall”-Easy的弹幕有够蠢的,只要站在她的正前方就没任何弹幕会碰到你; ZUN在《红魔乡》中介绍她时已经说她有点笨笨的了; 在ZUN放出《东方花映冢》的介绍图时,在图中把琪露诺放在了⑨的位置上,并以“⑨笨蛋”简单带过,从此“⑨”及“笨蛋”就成为她的别名了…… 所以琪露诺便得到了“笨蛋”的别称。 某日,琪露诺又2了…… 她写了N封信要装到N个信封里面,却全都装错了……现在想知道有多少种装错的可能性。 输入描述 Input Description 信和信封的数量N。 输出描述 Output Description 装错的可能性的数量。 样例输入 Sample Input 输入样例1 2 输入样例2 4 样例输出 Sample Output 输出样例1 1 输出样例2 9 数据范围及提示 Data Size & Hint 1≤N≤100 分类标签 Tags 动态规划 序列型DP 高精度 数学相关
/*高精度+错排公式.错排公式可以自己搞出来.递推:有n封信,第i封信装错的话有i-1种可能,设i-1其中一个为k,那么k有两种装法:(1):装到第i个信封里,此时剩下的i-2封信要装到i-2个信封里,就有f[i-2];(2):装到除i之外的信封里,这时i-1的作用和i一样,剩下的就有f[i-1]; so f[i]=(i-1)*(f[i-1]+f[i-2]) .*/#include#include #define MAXN 101using namespace std;int f[MAXN][1000001],n;int len(int x){ int i=100000-1; while(!f[x][i]&&i) i--; return i;}void add(int i,int l){ for(int j=0;j<=l;j++) { if(f[i][j]>9) { f[i][j+1]+=f[i][j]/10; f[i][j]%=10; } }}void slove(){ int l,l1; for(int i=3;i<=n;i++) { l=len(i-1); for(int j=0;j<=l;j++) { f[i][j]=f[i-1][j]+f[i-2][j]; } add(i,l); l1=len(i); for(int j=0;j<=l1;j++) { f[i][j]*=i-1; } add(i,l1); } l=len(n); for(int i=l;i>=0;i--) { printf("%d",f[n][i]); }}int main(){ scanf("%d",&n); f[2][0]=1; slove(); return 0;}