入力から解法がだいぶ見えてしまうかも。
https://yukicoder.me/problems/no/2152
問題
1~19の順列Pを考える。
Pの各要素について、その位置に来てよい値の候補が与えられる。
全条件を満たすPのうち、転倒数が奇数・偶数のものをそれぞれ求めよ。
解法
BitDPで、使用済みの値と、ここまでの転倒数の偶奇をもってPの先頭から決めていく。
int L[19]; int M[19]; ll dp[1<<19][2]; void solve() { int i,j,k,l,r,x,y; string s; FOR(i,19) { cin>>L[i]; FOR(j,L[i]) { cin>>x; M[i]|=1<<(x-1); } } dp[0][0]=1; int mask; FOR(mask,1<<19) FOR(y,2) { j=__builtin_popcount(mask); x=0; for(i=18;i>=0;i--) { if(mask&(1<<i)) { x^=1; } else if(M[j]&(1<<i)) { dp[mask^(1<<i)][y^x]+=dp[mask][y]; } } } cout<<dp[(1<<19)-1][0]<<" "<<dp[(1<<19)-1][1]<<endl; }
まとめ
★2.5でもいいかも。