\(\mathrm{dp}[i][j][k]\) を、「 下から \(i-1\) ビット目までが \(j\) と一致し、下から \(i\) ビット目以降が \(j\) と \(k\) ビット異なるような数に対して掛けられる値」と定義する動的計画法を考えます。

\(\mathrm{dp}[0][*][*]\) の初期値は \(1\) とし、入力の各 \((C_i,D_i,X_i)\) については、\(\mathrm{dp}[0][C_i][D_i]\) に \(X_i\) を掛ければよいです。遷移は \(i\) ビット目が \(j\) の \(i\) ビット目と異なるかで場合分けすることで行えます。

状態数が \(\mathrm{O}(N^2 2^N)\) 、遷移が \(\mathrm{O}(1)\) なのでこの問題を \(\mathrm{O}(N^22^N)\) で解くことが出来ます。