提出 #18011616

---

ソースコード 拡げる

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
const int N = 205;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;

int n, m, f[N], vis[N], p[N], c[N][N], fac[N], inv[N], ans;
char s[N];

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w;
}

int fpow(int x, int y)
{
	int res = 1;
	for( ; y; y >>= 1, x = 1ll * x * x % mod)
		if(y & 1) res = 1ll * res * x % mod;
	return res;
}

bool check(vector<int> res)
{
	queue<int> q;
	for(int i = 0; i <= m; i++) f[i] = vis[i] = p[i] = 0;
	for(int pos = 0, i = 1; i <= m; i++)
	{
		if(s[i] == 'b')
		{
			if(q.size()) f[i] = res[q.front()] - 2, p[q.front()] = 1, vis[i] = 1, q.pop();
		}
		else
			if(pos < res.size())
			{
				if(res[pos] > 1) q.push(pos);
				else p[pos] = 1;
				vis[i] = 1, pos++;
			}
	}
	for(int i = 0; i < res.size(); i++) if(!p[i]) return 0;
	for(int k = 0, i = m; i >= 1; i--)
		if(vis[i])
		{
			if(f[i])
			{
				if(k < f[i]) return 0;
				k -= f[i];
			}
		}
		else k++;
	return 1;
}

void dfs(int u, int l, int r, vector<int> res)
{
	if(!u)
	{
/*		for(auto v : res) printf("%d ", v);
		puts("");
*/		if(!check(res)) return;
/*		for(auto v : res) printf("%d ", v);
		puts("");
*/		int x = 1ll * c[n - l + r - 1][r - 1] * fac[res.size()] % mod, y = 0, z;
		while(res.size())
		{
			y = 0, z = res[res.size() - 1];
			while(res.size() && res[res.size() - 1] == z) y++, res.pop_back();
			x = 1ll * x * inv[y] % mod;
		}
		ans = (ans + x) % mod;
		return;
	}
	while(1)
	{
		dfs(u - 1, l, r, res);
		r += 2 * u, l += (l != 0) + (u == 1 ? 1 : 2 * u - 3);
		if(l > n) return;
		res.push_back(u);
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin);
#endif
	n = read <int> (), m = read <int> (), scanf("%s", s + 1);
	for(int i = 0; i <= 200; i++)
		for(int j = 0; j <= i; j++) c[i][j] = (!j ? 1 : (c[i - 1][j - 1] + c[i - 1][j]) % mod);
	for(int i = (fac[0] = 1); i <= 200; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[200] = fpow(fac[200], mod - 2);
	for(int i = 199; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	vector<int> res;
	dfs((n + 3) >> 1, 0, 1, res), printf("%d\n", ans);
	return 0; 
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘bool check(std::vector<int>)’:
./Main.cpp:43:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   43 |    if(pos < res.size())
      |       ~~~~^~~~~~~~~~~~
./Main.cpp:50:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   50 |  for(int i = 0; i < res.size(); i++) if(!p[i]) return 0;
      |                 ~~^~~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:97:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   97 |  n = read <int> (), m = read <int> (), scanf("%s", s + 1);
      |                                        ~~~~~^~~~~~~~~~~~~

ジャッジ結果