百度识图官网,站长工具seo查询5g5g,wordpress还原数据库备份,wordpress文本正题 题目大意 n∗nn*nn∗n的矩阵#xff0c;要求放nnn个雕塑#xff0c;要求每行每列都只有一个雕塑#xff0c;且不可以放在障碍物上。求方案总数。 解题思路
首先没有障碍物答案就是n!n!n!。 之后障碍物很少#xff0c;考虑容斥。
设fif_ifi为选iii个障碍物且这些障…正题 题目大意
n∗nn*nn∗n的矩阵要求放nnn个雕塑要求每行每列都只有一个雕塑且不可以放在障碍物上。求方案总数。 解题思路
首先没有障碍物答案就是n!n!n!。 之后障碍物很少考虑容斥。
设fif_ifi为选iii个障碍物且这些障碍物的位置必须放雕塑的方案总数。
然后答案显然 ans∑i0mfi∗(1−i%2∗2)ans\sum_{i0}^mf_i*(1-i\%2*2)ansi0∑mfi∗(1−i%2∗2) 也就是奇数加偶数减。 codecodecode
#includecstdio
#includecstring
#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 ans0;while(x)ans,x-x-x;return ans;
}
ll P(ll n){ll ans1;for(ll i1;in;i)ans*i;return ans;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld%lld,a[i].x,a[i].y);MS1m;for(ll i0;iMS;i){ll kn,flagtrue;memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));for(ll j1;jm;j)if((i(j-1))1){if(vx[a[j].x]||vy[a[j].y]){flagfalse;break;}k--;vx[a[j].x]1;vy[a[j].y]1;}ansflag*((count_one(i)1)?-1:1)*P(k);}printf(%lld,ans);
}
