A brief description of the topic, a little cumbersome, this GodFly’s treasure hunt.
Explanation: because there are only 18, DP is used.
First read the edge. R[i][j] represents the number of edges between I and J.
Define the state: f [i] [s] [w] means to stay at point i, the path set i s s, and the total cost i s w. The answer i s Sigma (f [n] [s] [q]), where s i s an arbitrary state.
Initialization: f[1][1][0]=1;
State transition equation: from I point, state s to t point, then there is
f[t][s|(1<<t-1)][(0+t×num[s])%2]+=f[i][s][0]×r[i][t]
f[t][s|(1<<t-1)][(1+t×num[s])%2]+=f[i][s][1]×r[i][t]
That is the next state plan number + = current scheme number * transfer path number.
It is important to enumerate the state s and enumerate I and T in each state.
Why? Because if s i s enumerated in I or t, there will be a case of “updating another state with a state that has not been updated”. The answer is wrong.
Finally, ans=sigma (f[n][s][q]) and Q are the query states.
> text begins.
Bit operation / DP Technology:
I bits is 1.
（1<<i-1）
Determine whether the second bit of state s i s 1 (determine whether it has been selected)
return (1<<i-1)&s
If 1, then (I and s are 1).
If it is 0, it will not be there.
