SRM 659 Div1 Medium CampLunch

想定解とはおそらく少し違う方法で解いた (定数倍高速化を頑張って TLE ギリギリなので、想定解が思いつくならそちらの方がよい。)

まず、i 日目で隣り合う 2 人がどうペアになるか全列挙し、高速ゼータ変換を行う。すると、i 日目の食事で、ペアにできない人の集合を固定したときに、何通りあるかが計算できる。
各人の状態を「前の日と2連続」、「次の日と2連続」、「どちらでもない」の 3 通りにして DP をすると、計算量が O(N*3^M)になる。(DP テーブルとして持つのは、「前の日と2連続」、「それ以外」の 2 通り)
定数倍高速化することで 1.95 sec くらいになる。(ローカルでは、サンプルが、3.6 sec)

#define L 16
ll dp[L+1][1<<L];
ll dp2[1<<L];
vector<string> a;

class CampLunch {
	public:
	int f(int i, int j){
		return a[i][j]-'A';
	}
	int count(int n, int m, vector <string> a_) {
		a=a_;
		mset(dp, 0);
		ll mask = (1<<m)-1;
		dp[0][0] = 1;
		rep(i, n){
			mset(dp2, 0);
			rep(j, 1<<(m-1)){
				int j2 = j;
				bool ok = true;
				while(j2){
					if((j2&3)==3) ok = false;
					j2 >>= 1;
				}
				if(!ok) continue;
				int t = 0;
				rep(k, m-1){
					if(1&(j>>k)){
						t |= 1<<f(i, k);
						t |= 1<<f(i, k+1);
					}
				}
				dp2[t^mask]++;
			}
			rep(j, m) rep(b, 1<<m) if(0==(1&(b>>j))) dp2[b] += dp2[b|(1<<j)];
			rep(j, 1<<m){
				for(int k = j; ;k=(k-1)&j){
					(dp[i+1][k]+=dp[i][j&~k]*dp2[j]);
					if(k==0) break;
				}
			}
			rep(j, 1<<m) dp[i+1][j]%=mod;
		}
		return dp[n][0];
	}
};