生活随笔
收集整理的這篇文章主要介紹了
bzoj4563放棋子
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
每一行只有一個障礙，每一列也只有一個障礙
可以把某些行交換一下，得到類似下面的格式
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
交換之后并不影響方案數
然后，把每一列壓縮成一個位置，問題轉化為每一個位置放一個棋子且不能放在原來的位置（第i個個棋子原來的位置是i）
轉化為錯排公式
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000000
#define LL long long
#define maxn 5005
using namespace std;
int n;
struct Bignum
{LL s[maxn];
int len;Bignum(){
memset(s,
0,
sizeof(s)); len=
0; }
}A,B,C;
Bignum
operator + (
const Bignum a,
const Bignum b)
{Bignum c;
int i=
1;LL x=
0;
while(i<=a.len||i<=b.len){c.s[i]=x+a.s[i]+b.s[i];x=c.s[i]/mod;c.s[i]%=mod; i++;}c.len=max(a.len,b.len);
while(x){ c.s[++c.len]=x%mod; x/=mod;}
while(c.len&&!c.s[c.len]) c.len--;
return c;
}
Bignum
operator *(
const Bignum a,
int b)
{Bignum c;c.len=a.len;LL x=
0;
for(
int i=
1;i<=a.len;i++){c.s[i]=a.s[i]*(LL)b+x;x=c.s[i]/mod;c.s[i]%=mod;}
while(x){ c.s[++c.len]=x%mod; x/=mod; }
while(c.len&&!c.s[c.len]) c.len--;
return c;
}
void print(Bignum &a)
{
printf(
"%lld",a.s[a.len]);
for(
int i=a.len-
1;i>=
1;i--)
printf(
"%09lld",a.s[i]);
printf(
"\n");
}
int main()
{
scanf(
"%d",&n);
int x;
for(
int i=
1;i<=n;i++)
for(
int j=
1;j<=n;j++)
scanf(
"%d",&x);
if(n==
1){
printf(
"0\n");
return 0; }
if(n==
2){
printf(
"1\n");
return 0; }A.len=
1; A.s[
1]=
0; B.len=
1; B.s[
1]=
1;
for(
int i=
3;i<=n;i++){ C=(A+B)*(LL)(i-
1);A=B;B=C;}print(C);
return 0;
}
轉載于:https://www.cnblogs.com/hunterxhunterl/p/7780658.html
總結
以上是生活随笔為你收集整理的bzoj4563放棋子的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
