?

題目描述?Description

給你一個(gè)N*N的矩陣，每行有一個(gè)障礙，數(shù)據(jù)保證任意兩個(gè)障礙不在同一行，任意兩個(gè)障礙不在同一列，要求你在 這個(gè)矩陣上放N枚棋子（障礙的位置不能放棋子），要求你放N個(gè)棋子也滿足每行只有一枚棋子，每列只有一枚棋的限制，求有多少種方案。

輸入描述?Input Description

第一行一個(gè)N，接下來一個(gè)N*N的矩陣。N<=200,0表示沒有障礙，1表示有障礙，輸入格式參考樣例

輸出描述?Output Description

一個(gè)整數(shù)，即合法的方案數(shù)。

樣例輸入 Sample Input

2 0 1 1 0

樣例輸出 Sample Output

1

數(shù)據(jù)范圍及提示 Data Size & Hint

仔細(xì)讀完題發(fā)現(xiàn)輸入的那個(gè)矩陣一點(diǎn)用也沒有，因?yàn)榭梢酝ㄟ^平移變成障礙全在對角線上的圖。繼續(xù)來思考這個(gè)問題，問題轉(zhuǎn)化為將1~n這N個(gè)數(shù)排列，要求第i個(gè)數(shù)不能排列在第i個(gè)位置上，這被稱之為錯排問題。考慮怎么遞推。設(shè)f(i)表示i個(gè)數(shù)的錯拍方案數(shù)，我們要將第i個(gè)數(shù)插入之前i-1個(gè)數(shù)，（因?yàn)榈趇個(gè)數(shù)不能插在i位置上），假如i將插在j位置上，j有兩種選擇，一種是j填到i的位置上，于是問題就轉(zhuǎn)化為了f(i-2)；另一種j填到另外i-2的位置中，我們設(shè)新填的位置為k(k!=i && k!=j),現(xiàn)在我們就需要把k這個(gè)數(shù)再放在i-1個(gè)數(shù)中了，即f(i-1),由于j有i-1種情況，所以我們最后再乘一個(gè)(i-1)，所以遞推公式就變成了f(i)=(f(i-1)+f(i-2))*(i-1)，推到這一步，我們再寫一個(gè)高精度支持高加高，高乘低即可。

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #include<cstring> using namespace std; typedef long long LL; typedef pair<int,int> PII; #define mem(a,b) memset(a,b,sizeof(a)) inline int read() {int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } const int maxn=1010; struct data {int l,v[maxn];data(){l=1;mem(v,0);}data operator = (const int& s){v[1]=s;while(v[l]>9)v[l+1]=v[l]/10,v[l]%=10,l++;return *this;}data operator = (const data& s){l=s.l;for(int i=1;i<=l;i++)v[i]=s.v[i];return *this;}data operator + (const data& s)const{data c;c.l=max(l,s.l)+1;for(int i=1;i<=c.l;i++)c.v[i]=v[i]+s.v[i];for(int i=1;i<c.l;i++)if(c.v[i]>9)c.v[i+1]+=c.v[i]/10,c.v[i]%=10;while(c.v[c.l]>9)c.v[c.l+1]=c.v[c.l]/10,c.v[c.l]%=10,c.l++;while(!c.v[c.l])c.l--;return c;}data operator * (const int& s)const{data c;c.l=l;for(int i=1;i<=c.l;i++)c.v[i]=v[i]*s;for(int i=1;i<c.l;i++)if(c.v[i]>9)c.v[i+1]+=c.v[i]/10,c.v[i]%=10;while(c.v[c.l]>9)c.v[c.l+1]=c.v[c.l]/10,c.v[c.l]%=10,c.l++;while(!c.v[c.l])c.l--;return c;} }f[210]; void print(data a){for(int i=a.l;i;i--)printf("%d",a.v[i]);} int n; int main() {n=read();f[1]=0;f[2]=1;for(int i=3;i<=n;i++)f[i]=(f[i-1]+f[i-2])*(i-1);print(f[n]);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/FYH-SSGSS/p/6918461.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的BZOJ4563[Haoi2016]放棋子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。