Submission #3464820
Source Code Expand
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
freopen ("F.in", "r", stdin);
freopen ("F.out", "w", stdout);
}
const int N = 5010, Mod = 1e9 + 7;
int n; char str[N];
inline int fpm(int x, int power) {
int res = 1;
for (; power; power >>= 1, x = 1ll * x * x % Mod)
if (power & 1) res = 1ll * res * x % Mod;
return res;
}
int dp[N][N];
inline void Add(int &a, int b) {
if ((a += b) >= Mod) a -= Mod;
}
int main () {
n = read();
scanf ("%s", str + 1);
int len = strlen(str + 1);
dp[0][0] = 1;
For (i, 0, n - 1) For (j, 0, i) {
Add(dp[i + 1][j + 1], dp[i][j] * 2 % Mod);
Add(dp[i + 1][max(0, j - 1)], dp[i][j]);
}
printf ("%d\n", 1ll * dp[n][len] * fpm(fpm(2, len), Mod - 2) % Mod);
return 0;
}
Submission Info
Submission Time
2018-10-25 11:03:05+0900
Task
F - Unhappy Hacking
User
zjp_shadow
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1529 Byte
Status
AC
Exec Time
102 ms
Memory
96512 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:57:68: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
printf ("%d\n", 1ll * dp[n][len] * fpm(fpm(2, len), Mod - 2) % Mod);
^
./Main.cpp: In function ‘void File()’:
./Main.cpp:23:30: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen ("F.in", "r", stdin);
^
./Main.cpp:24:32: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen ("F.out", "w", stdout);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:47:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf ("%s", str + 1);
...
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
1 ms
256 KB
0_02
AC
3 ms
4736 KB
0_03
AC
99 ms
96512 KB
1_04
AC
1 ms
256 KB
1_05
AC
2 ms
4736 KB
1_06
AC
2 ms
4736 KB
1_07
AC
2 ms
4736 KB
1_08
AC
2 ms
4736 KB
1_09
AC
2 ms
4736 KB
1_10
AC
2 ms
4736 KB
1_11
AC
2 ms
4736 KB
1_12
AC
3 ms
4736 KB
1_13
AC
3 ms
4736 KB
1_14
AC
3 ms
4736 KB
1_15
AC
2 ms
4736 KB
1_16
AC
2 ms
4736 KB
1_17
AC
2 ms
4736 KB
1_18
AC
2 ms
4736 KB
1_19
AC
2 ms
4736 KB
1_20
AC
1 ms
512 KB
1_21
AC
2 ms
2688 KB
1_22
AC
1 ms
512 KB
1_23
AC
2 ms
4736 KB
1_24
AC
2 ms
4736 KB
2_25
AC
100 ms
96512 KB
2_26
AC
99 ms
96512 KB
2_27
AC
99 ms
96512 KB
2_28
AC
99 ms
96512 KB
2_29
AC
99 ms
96512 KB
2_30
AC
99 ms
96512 KB
2_31
AC
102 ms
96512 KB
2_32
AC
100 ms
96512 KB
2_33
AC
100 ms
96512 KB
2_34
AC
100 ms
96512 KB
2_35
AC
100 ms
96512 KB
2_36
AC
99 ms
96384 KB
2_37
AC
99 ms
96384 KB
2_38
AC
100 ms
96384 KB
2_39
AC
99 ms
96384 KB
2_40
AC
82 ms
86656 KB
2_41
AC
47 ms
62080 KB
2_42
AC
95 ms
94848 KB
2_43
AC
57 ms
70272 KB
2_44
AC
6 ms
12928 KB