题目：涂抹果酱
思路：使用3进制状压。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 10000
#define maxm 5
#define maxs 250
#define md 1000000
#define ll long longint n,m,k;
vector<int> state;
int f[maxn+5][maxs+5];void read(int& x) {scanf("%d",&x);
}int makeid(int* x) {int s=0;for(int i=1;i<=m;i++) {s=s*3+x[i];}return s;
}bool judge(int x) {int y=-1;for(int i=1;i<=m;i++) {if(y==x%3) return false;y=x%3;x/=3;}return true;
}void makestate() {int M=1;for(int i=1;i<=m;i++) M*=3;for(int i=0;i<M;i++) {if(judge(i)) state.push_back(i);}
}bool ok(int x,int y) {for(int i=1;i<=m;i++) {if(y%3==x%3) return false;x/=3;y/=3;}return true;
}int dp(int lne,int init) {memset(f,0,sizeof(f));f[1][init]=1;for(int i=2;i<=lne;i++) {for(int j=0;j<state.size();j++) {int x=state[j];for(int l=0;l<state.size();l++) {int y=state[l];if(!ok(x,y)) continue;f[i][x]=((ll)f[i-1][y]+f[i][x])%md;}}}int ans=0;for(int j=0;j<state.size();j++) {int y=state[j];ans=((ll)ans+f[lne][y])%md;}return ans;
}int main() {read(n);read(m);read(k);int x[maxm+5];for(int i=1;i<=m;i++) read(x[i]),x[i]--;int y=makeid(x);makestate();printf("%d",(ll)dp(k,y)*dp(n+1-k,y)%md);return 0;
}