提出 #837686


ソースコード 拡げる

Copy
/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 200000;

int n, m;
string st;
int ways[5050][5050];
int walk[5050][5050];

long long fact[N];

long long pw(long long a, long long b)
{
	if (b == 0)
		return 1;
	if (b % 2)
		return a*pw(a, b - 1) % bs;
	return pw(a*a%bs, b / 2);
}

long long inv(long long x)
{
	return pw(x, bs - 2);
}

void add(int&a, int b)
{
	a += b;
	if (a >= bs)
		a -= bs;
}


long long C(long long n, long long m)
{
	if (m > n)
		return 0;
	long long res = fact[n];
	res *= inv(fact[m]);
	res %= bs;
	res *= inv(fact[n - m]);
	res %= bs;
	return res;
}

int main(){
	//freopen("fabro.in","r",stdin);
	//freopen("fabro.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin >> n;
	cin >> st;
	m = st.size();

	fact[0] = 1;
	for (int i = 0; i < N; i++)
	{
		fact[i] = fact[i - 1] * i%bs;
	}

	ways[0][0] = 1;
	for (int i = 0; i < 5000; i++)
	{
		for (int j = 0; j <= 5000; j++)
		{
			add(ways[i + 1][j + 1], ways[i][j] * 2 % bs);
			add(ways[i + 1][max(j - 1, 0)], ways[i][j]);
		}
	}

	walk[0][0] = 1;
	for (int i = 0; i <= 5000; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			add(walk[i + 1][j+1], walk[i][j]);
			if (j > 1)
				add(walk[i + 1][j - 1], walk[i][j]);
		}
	}

	long long ans = 0;

	for (int start = 0; start <= n; start++)
	{
		int res1 = ways[start][0];
		int rem = n - start;
		if (rem % 2 !=m%2)
			continue;
		if (rem < m)
			continue;
		//cout << res1 << " " << start << endl;

		int rem_ways = walk[n - start][m];
		res1 = 1ll * res1*rem_ways%bs;
		//cout << res1 << endl;
		int ohead_let = (rem - m) / 2;
		//cout << ohead_let << endl;

		//res1 = res1 * 1ll * C(ohead_let + m, m) % bs;
		res1 = res1 * 1ll * pw(2, ohead_let) % bs;
		//cout << res1 << endl;
		ans += res1;
		ans %= bs;
	}
	cout << ans << endl;

	cin.get(); cin.get();
	return 0;
}

提出情報

提出日時
問題 F - バイナリハック
ユーザ LeBron
言語 C++14 (GCC 5.4.1)
得点 800
コード長 2692 Byte
結果 AC
実行時間 777 ms
メモリ 167424 KB

コンパイルエラー

./Main.cpp:33:0: warning: "M_PI" redefined
 #define M_PI 3.141592653589793
 ^
In file included from /usr/include/c++/5/cmath:44:0,
                 from /usr/include/c++/5/complex:44,
                 from ./Main.cpp:10:
/usr/include/math.h:372:0: note: this is the location of the previous definition
 # define M_PI  3.14159265358979323846 /* pi */
 ^

ジャッジ結果

セット名 Sample Sub1 Sub2
得点 / 配点 0 / 0 400 / 400 400 / 400
結果
AC × 3
AC × 23
AC × 44
セット名 テストケース
Sample 0_01, 0_02, 0_03
Sub1 0_01, 0_02, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24
Sub2 0_01, 0_02, 0_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 2_25, 2_26, 2_27, 2_28, 2_29, 2_30, 2_31, 2_32, 2_33, 2_34, 2_35, 2_36, 2_37, 2_38, 2_39, 2_40, 2_41, 2_42, 2_43, 2_44
ケース名 結果 実行時間 メモリ
0_01 AC 763 ms 167424 KB
0_02 AC 759 ms 167424 KB
0_03 AC 760 ms 167424 KB
1_04 AC 765 ms 167424 KB
1_05 AC 772 ms 167424 KB
1_06 AC 759 ms 167424 KB
1_07 AC 758 ms 167424 KB
1_08 AC 763 ms 167424 KB
1_09 AC 759 ms 167424 KB
1_10 AC 763 ms 167424 KB
1_11 AC 762 ms 167424 KB
1_12 AC 771 ms 167424 KB
1_13 AC 761 ms 167424 KB
1_14 AC 760 ms 167424 KB
1_15 AC 761 ms 167424 KB
1_16 AC 761 ms 167424 KB
1_17 AC 762 ms 167424 KB
1_18 AC 755 ms 167424 KB
1_19 AC 763 ms 167424 KB
1_20 AC 777 ms 167424 KB
1_21 AC 764 ms 167424 KB
1_22 AC 772 ms 167424 KB
1_23 AC 763 ms 167424 KB
1_24 AC 763 ms 167424 KB
2_25 AC 769 ms 167424 KB
2_26 AC 765 ms 167424 KB
2_27 AC 757 ms 167424 KB
2_28 AC 762 ms 167424 KB
2_29 AC 762 ms 167424 KB
2_30 AC 762 ms 167424 KB
2_31 AC 762 ms 167424 KB
2_32 AC 757 ms 167424 KB
2_33 AC 759 ms 167424 KB
2_34 AC 759 ms 167424 KB
2_35 AC 763 ms 167424 KB
2_36 AC 757 ms 167424 KB
2_37 AC 766 ms 167424 KB
2_38 AC 763 ms 167424 KB
2_39 AC 769 ms 167424 KB
2_40 AC 759 ms 167424 KB
2_41 AC 771 ms 167424 KB
2_42 AC 770 ms 167424 KB
2_43 AC 762 ms 167424 KB
2_44 AC 761 ms 167424 KB