Submission #1453928
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b) ((a >> b) & 1)
#define bitset(a,b) ( a |= (1 << b))
#define bitunset(a,b) (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
std::fill((T*)array, (T*)(array + N), val);
}
template<int MOD>
struct ModInt{
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) {}
ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
signed a = x, b = MOD, u = 1, v = 0;
while (b) {
signed t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
if (u < 0) u += Mod;
ModInt res; res.x = (unsigned)u;
return res;
}
};
typedef ModInt<1000000007> mint;
ll mod_pow(ll x, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * x%mod;
x = x*x%mod;
n >>= 1;
}
return res;
}
signed main() {
int n;
string str;
cin >> n >> str;
mint dp[5002][5002];
dp[0][0] = 1;
rep(i, 1, n+1){
REP(j, n+1){
dp[i][j] += (j ? dp[i - 1][j - 1]*2 : dp[i-1][j]) + dp[i-1][j + 1];
}
}
printf("%d\n", (dp[n][str.length()] / (mint)mod_pow(2, str.length(), MODU)).get());
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Unhappy Hacking |
User |
Gear |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
3273 Byte |
Status |
AC |
Exec Time |
91 ms |
Memory |
98048 KB |
Judge Result
Set Name |
Sample |
Sub1 |
Sub2 |
Score / Max Score |
0 / 0 |
400 / 400 |
400 / 400 |
Status |
|
|
|
Set Name |
Test Cases |
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 |
Case Name |
Status |
Exec Time |
Memory |
0_01 |
AC |
30 ms |
97920 KB |
0_02 |
AC |
30 ms |
97920 KB |
0_03 |
AC |
91 ms |
97920 KB |
1_04 |
AC |
29 ms |
97920 KB |
1_05 |
AC |
30 ms |
97920 KB |
1_06 |
AC |
30 ms |
97920 KB |
1_07 |
AC |
30 ms |
97920 KB |
1_08 |
AC |
30 ms |
97920 KB |
1_09 |
AC |
30 ms |
97920 KB |
1_10 |
AC |
30 ms |
97920 KB |
1_11 |
AC |
30 ms |
97920 KB |
1_12 |
AC |
30 ms |
97920 KB |
1_13 |
AC |
30 ms |
97920 KB |
1_14 |
AC |
30 ms |
97920 KB |
1_15 |
AC |
30 ms |
97920 KB |
1_16 |
AC |
30 ms |
97920 KB |
1_17 |
AC |
30 ms |
97920 KB |
1_18 |
AC |
30 ms |
97920 KB |
1_19 |
AC |
30 ms |
97920 KB |
1_20 |
AC |
30 ms |
97920 KB |
1_21 |
AC |
30 ms |
97920 KB |
1_22 |
AC |
30 ms |
97920 KB |
1_23 |
AC |
30 ms |
97920 KB |
1_24 |
AC |
30 ms |
97920 KB |
2_25 |
AC |
91 ms |
97920 KB |
2_26 |
AC |
91 ms |
97920 KB |
2_27 |
AC |
91 ms |
98048 KB |
2_28 |
AC |
91 ms |
98048 KB |
2_29 |
AC |
91 ms |
98048 KB |
2_30 |
AC |
91 ms |
97920 KB |
2_31 |
AC |
91 ms |
98048 KB |
2_32 |
AC |
91 ms |
97920 KB |
2_33 |
AC |
91 ms |
98048 KB |
2_34 |
AC |
91 ms |
98048 KB |
2_35 |
AC |
91 ms |
98048 KB |
2_36 |
AC |
91 ms |
98048 KB |
2_37 |
AC |
91 ms |
98048 KB |
2_38 |
AC |
91 ms |
98048 KB |
2_39 |
AC |
91 ms |
98048 KB |
2_40 |
AC |
78 ms |
98048 KB |
2_41 |
AC |
54 ms |
97920 KB |
2_42 |
AC |
88 ms |
98048 KB |
2_43 |
AC |
62 ms |
97920 KB |
2_44 |
AC |
31 ms |
97920 KB |