Submission #839587
Source Code Expand
#include <iostream> #include <cstdio> #include <cassert> #include <cstring> #include <vector> #include <valarray> #include <array> #include <queue> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <algorithm> #include <cmath> #include <complex> #include <random> #define y0 kyuridenamida #define y1 kyuridenanmaida using namespace std; using ll = long long; using ull = unsigned long long; constexpr int TEN(int n) {return (n==0)?1:10*TEN(n-1);} template<class T> T pow(T x, ll n) { T r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } template<uint MD> struct ModInt { uint v; ModInt() : v{0} {} ModInt(ll v) : v{normS(v%MD+MD)} {} static uint normS(const uint &x) {return (x<MD)?x:x-MD;}; static ModInt make(const uint &x) {ModInt m; m.v = x; return m;} const ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));} const ModInt operator-(const ModInt &r) const {return make(normS(v+normS(MD-r.v)));} const ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);} ModInt& operator+=(const ModInt &r) {return *this=*this+r;} ModInt& operator-=(const ModInt &r) {return *this=*this-r;} ModInt& operator*=(const ModInt &r) {return *this=*this*r;} static ModInt inv(const ModInt &x) { return pow(ModInt(x), MD-2); } }; // ここまでテンプレ using Mint = ModInt<TEN(9)+7>; const int MN = 2*5050; Mint p2[MN]; Mint fact[MN], iFac[MN]; void first() { p2[0] = 1; for (int i = 1; i < MN; i++) { p2[i] = p2[i-1]*2; } fact[0] = 1; for (int i = 1; i < MN; i++) { fact[i] = fact[i-1]*i; } iFac[MN-1] = Mint::inv(fact[MN-1]); for (int i = MN-1; i >= 1; i--) { iFac[i-1] = iFac[i]*i; } } Mint C(int x, int y) { return fact[x]*iFac[y]*iFac[x-y]; } Mint K(int x, int y) { //(0, 0)から(x, y)へ移動する経路数 if (x < 0 or y < 0) return 0; return C(x+y, x); } Mint K(int x0, int y0, int x1, int y1) { //(x0, y0)から(x1, y1)へx<yを通らずに移動する経路数 int x2 = y1-1, y2 = x1+1; return K(x1-x0, y1-y0) - K(x2-x0, y2-y0); } Mint calc(int N, int M) { //(0, -M)から(N-i, -M+i)へ Mint ans = 0; for (int i = 0; i <= N; i++) { if (N-i < -M+i) break; ans += K(0, -M, N-i, -M+i) * p2[i]; } return ans; } int main() { first(); int N; string s; cin >> N >> s; int M = (int)s.size(); Mint ans = calc(N, M) - calc(N, M-1); ans *= pow(Mint::inv(2), M); cout << ans.v << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Unhappy Hacking |
User | yosupo |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2758 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 384 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 | 5 ms | 384 KB |
0_02 | AC | 5 ms | 384 KB |
0_03 | AC | 5 ms | 384 KB |
1_04 | AC | 5 ms | 384 KB |
1_05 | AC | 5 ms | 384 KB |
1_06 | AC | 5 ms | 384 KB |
1_07 | AC | 5 ms | 384 KB |
1_08 | AC | 5 ms | 384 KB |
1_09 | AC | 5 ms | 384 KB |
1_10 | AC | 5 ms | 384 KB |
1_11 | AC | 5 ms | 384 KB |
1_12 | AC | 5 ms | 384 KB |
1_13 | AC | 5 ms | 384 KB |
1_14 | AC | 5 ms | 384 KB |
1_15 | AC | 5 ms | 384 KB |
1_16 | AC | 5 ms | 384 KB |
1_17 | AC | 5 ms | 384 KB |
1_18 | AC | 5 ms | 384 KB |
1_19 | AC | 5 ms | 384 KB |
1_20 | AC | 5 ms | 384 KB |
1_21 | AC | 5 ms | 384 KB |
1_22 | AC | 5 ms | 384 KB |
1_23 | AC | 5 ms | 384 KB |
1_24 | AC | 5 ms | 384 KB |
2_25 | AC | 5 ms | 384 KB |
2_26 | AC | 5 ms | 384 KB |
2_27 | AC | 5 ms | 384 KB |
2_28 | AC | 5 ms | 384 KB |
2_29 | AC | 5 ms | 384 KB |
2_30 | AC | 5 ms | 384 KB |
2_31 | AC | 5 ms | 384 KB |
2_32 | AC | 5 ms | 384 KB |
2_33 | AC | 5 ms | 384 KB |
2_34 | AC | 5 ms | 384 KB |
2_35 | AC | 5 ms | 384 KB |
2_36 | AC | 5 ms | 384 KB |
2_37 | AC | 5 ms | 384 KB |
2_38 | AC | 5 ms | 384 KB |
2_39 | AC | 5 ms | 384 KB |
2_40 | AC | 5 ms | 384 KB |
2_41 | AC | 5 ms | 384 KB |
2_42 | AC | 5 ms | 384 KB |
2_43 | AC | 5 ms | 384 KB |
2_44 | AC | 5 ms | 384 KB |