首页 > 代码库 > [BZOJ 4563][Haoi2016]放棋子（错排公式）
[BZOJ 4563][Haoi2016]放棋子（错排公式）
Description
给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。
Solution
其实和给出的障碍没什么关系，可以直接上错排公式（因为一开始的障碍可以看做一个排列，然后放棋子等同于要你生成一个新的不能有和原来位置相同元素的排列）
f[n]=(f[n-1]+f[n-2])*(n-1)（为什么的话上一篇里有说QwQ）
要加高精！
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int n;struct Bign{ static const int base=1000000; int len,s[1000]; Bign(){len=1;memset(s,0,sizeof(s));} Bign(int num){*this=num;} Bign operator = (int num) { len=0; while(num) { s[len++]=num%base; num/=base; } return *this; } Bign operator + (const Bign& b) { Bign c;c.len=0; for(int i=0,g=0;g||i<max(len,b.len);i++) { g+=s[i]+b.s[i]; c.s[c.len++]=g%base; g/=base; } return c; } Bign operator * (const int& b) { Bign c;c.len=0; for(int i=0;i<len||c.s[c.len];i++) { c.s[i]+=s[i]*b; c.s[i+1]+=c.s[i]/base; c.s[i]%=base; ++c.len; } return c; } void print() { printf("%d",s[len-1]); for(int i=len-2;i>=0;i--) printf("%06d",s[i]); }}F[2];int main(){ scanf("%d",&n); F[0]=1,F[1]=0; for(int i=2;i<=n;i++) { F[0]=(F[0]+F[1])*(i-1); swap(F[0],F[1]); } F[1].print(); return 0;}
[BZOJ 4563][Haoi2016]放棋子（错排公式）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。