正題

---

題目大意

$n?n$的矩陣，要求放$n$個(gè)雕塑，要求每行每列都只有一個(gè)雕塑，且不可以放在障礙物上。求方案總數(shù)。

---

解題思路

首先沒(méi)有障礙物答案就是$n!$。
之后障礙物很少，考慮容斥。

設(shè)$f_i$為選$i$個(gè)障礙物且這些障礙物的位置必須放雕塑的方案總數(shù)。

然后答案顯然
$$ans=\sum _{i=0}^m{f}_i?(1?i\%2?2)$$
也就是奇數(shù)加，偶數(shù)減。

---

$code$

#include<cstdio> #include<cstring> #define N 25 #define ll long long using namespace std; struct node{ll x,y; }a[15]; ll n,m,MS,ans; bool vx[N],vy[N]; ll count_one(ll x){ll ans=0;while(x)ans++,x-=x&-x;return ans; } ll P(ll n){ll ans=1;for(ll i=1;i<=n;i++)ans*=i;return ans; } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++)scanf("%lld%lld",&a[i].x,&a[i].y);MS=1<<m;for(ll i=0;i<MS;i++){ll k=n,flag=true;memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));for(ll j=1;j<=m;j++)if((i>>(j-1))&1){if(vx[a[j].x]||vy[a[j].y]){flag=false;break;}k--;vx[a[j].x]=1;vy[a[j].y]=1;}ans+=flag*((count_one(i)&1)?-1:1)*P(k);}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3059-雕塑【容斥,数论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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