P4590

怎么这么多忘交的
一起发的原因还是vjudge

#include<bits/stdc++.h>
using namespace std;
int read() {
	int x = 0;
	bool op = 0;
	char c = getchar();
	while(!isdigit(c))op |= (c == '-'), c = getchar();
	while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return op ? -x : x;
}
const int N = 1010;
const int P = 1e9 + 7;
int n, k;
int f[2][1 << 15][3], cnt[1 << 15], m[300], g[2][20], ans[20];
char s[20];
void decode(int S) {
	memset(g[0], 0, sizeof(g[0]));
	for(int i = 0; i < k; i++)g[0][i + 1] = (S >> i & 1);
	for(int i = 1; i <= k; i++)g[0][i] += g[0][i - 1];
	return ;
}
int encode() {
	int S = 0;
	for(int i = 1; i <= k; i++) {
		int now = g[1][i] - g[1][i - 1];
		S ^= now * (1 << (i - 1));
	}
	return S;
}
void trans(int cur, int S, int c, int p, int x) {
	if((p == 2 && c == 2) || x == 0)return ;
	int nxt = (c == 0) ? 1 : 0;
	if(p == 0 && c == 0)nxt = 1;
	else if(p == 1 && c == 1)nxt = 2;
	decode(S);
	memset(g[1], 0, sizeof(g[1]));
	for(int i = 1; i <= k; i++) {
		if(m[s[i]] == c) {
			g[1][i] = max(g[1][i], g[0][i - 1] + 1);
		}
		g[1][i] = max(g[1][i], max(g[0][i], g[1][i - 1]));
	}
	int ns = encode();
	f[cur][ns][nxt] = (f[cur][ns][nxt] + x) % P;
	return ;
}
int main() {
	n = read();
	k = read();
	scanf("%s", s + 1);
	m['N'] = 0;
	m['O'] = 1;
	m['I'] = 2;
	int maxi = 1 << k, cur = 0;
	f[cur][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		cur = cur ^ 1;
		memset(f[cur], 0, sizeof(f[cur]));
		for(int j = 0; j < maxi; j++) {
			for(int p = 0; p < 3; p++) {
				trans(cur, j, p, 0, f[cur ^ 1][j][0]);
				trans(cur, j, p, 1, f[cur ^ 1][j][1]);
				trans(cur, j, p, 2, f[cur ^ 1][j][2]);
			}
		}
	}
	cnt[0] = 0;
	for(int i = 1; i < maxi; i++)cnt[i] = cnt[i >> 1] + (i & 1);
	for(int i = 0; i < maxi; i++) {
		for(int p = 0; p < 3; p++) {
			ans[cnt[i]] = (ans[cnt[i]] + f[cur][i][p]) % P;
		}
	}
	for(int i = 0; i <= k; i++)printf("%d\n", ans[i]);
	return 0;
}