Submission #1815949
Source Code Expand
//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP
/*
* temp.cpp
*
* Created on: 2012-7-18
* Author: BSBandme
*/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <tuple>
using namespace std;
#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif
#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif
#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}
#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template <typename t, typename t1>
t min1(t a, t1 b) { return a < b ? a : b; }
template <typename t, typename... arg>
t min1(t a, arg... arr) { return min1(a, min1(arr...)); }
template <typename t, typename t1>
t max1(t a, t1 b) { return a > b ? a : b; }
template <typename t, typename... arg>
t max1(t a, arg... arr) { return max1(a, max1(arr...)); }
#endif
inline int jud(double a, double b){
if(abs(a) < eps && abs(b) < eps) return 0;
else if(abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
if(a < b) return -1;
return 1;
}
template <typename t> inline int jud(t a, t b){
if(a < b) return -1;
if(a == b) return 0;
return 1;
}
// f_lb == 1代表返回相同的一串的左边界,f_small == 1代表返回如果没有寻找的值返回小的数
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
if(na == 0) return 0;
int be = 0, en = na - 1;
if(*a <= *(a + na - 1)){
if(f_lb == 0) while(be < en){
int mid = (be + en + 1) / 2;
if(jud(*(a + mid), val) != 1) be = mid;
else en = mid - 1;
}else while(be < en){
int mid = (be + en) / 2;
if(jud(*(a + mid), val) != -1) en = mid;
else be = mid + 1;
}
if(f_small && jud(*(a + be), val) == 1) be--;
if(!f_small && jud(*(a + be), val) == -1) be++;
} else {
if(f_lb) while(be < en){
int mid = (be + en + 1) / 2;
if(jud(*(a + mid), val) != -1) be = mid;
else en = mid - 1;
}else while(be < en){
int mid = (be + en) / 2;
if(jud(*(a + mid), val) != 1) en = mid;
else be = mid + 1;
}
if(!f_small && jud(*(a + be), val) == -1) be--;
if(f_small && jud(*(a + be), val) == 1) be++;
}
return be;
}
template <class T> inline T lowb(T num) {return num & (-num); }
#ifdef GPP
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
#else
#endif
long long pow(long long n, long long m, long long mod = 0){
if(m < 0) return 0;
long long ans = 1;
long long k = n;
while(m){
if(m & 1) {
ans *= k;
if(mod) ans %= mod;
}
k *= k;
if(mod) k %= mod;
m >>= 1;
}
return ans;
}
#define MOD 1000000007
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
if(mod == -1) mod = MOD;
a += b;
while(a >= mod) a -= mod;
while(a < 0) a += mod;
}
template <class t>
void output1(t arr) {
for(int i = 0; i < (int)arr.size(); i++)
cerr << arr[i] << ' ';
cerr << endl;
}
template <class t>
void output2(t arr) {
for(int i = 0; i < (int)arr.size(); i++)
output1(arr[i]);
}
//....................密..........封..........线..........下..........禁..........止..........hack...............................................
const int mod = 998244353;
const int maxn = 500100;
ll fac[maxn];
ll invfac[maxn];
int n, m;
string stra, strb, strc, strd;
ll ans = 0;
ll c(int a, int b) {
if (a == b) return 1;
if (b < 0) return 0;
if (b > a) return 0;
return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}
int cnt1(const string &str) {
int a = 0;
for (int i = 0; i < (int)str.length(); i++) {
a += str[i] == '1';
}
return a;
}
void solve() {
ll rsum = 1;
ll la = cnt1(stra), lb = cnt1(strb), ora = la, orb = lb, lc = cnt1(strc), ld = cnt1(strd);
for (int i = n - 1; i >= 0; i--) {
if (stra[i] != '1' && strb[i] != '1') {
continue;
}
ll mul = 1;
if (stra[i] == '1' && strb[i] == '1') {
mul++;
}
la -= stra[i] == '1', lb -= strb[i] == '1';
rsum = rsum * mul % mod;
ans += rsum * c(la + lb + lc - 1, lc - 1);
ans %= mod;
rsum += c(ora - la + orb - lb + ld - 1, ld - 1);
rsum %= mod;
}
}
int main() {
//............................不要再忘了检查maxn大小了!!!!BSBandme你个SB!!!!...................................................
ios_base::sync_with_stdio(0);
#ifdef DEBUG //......................................................................................................
freopen("input.txt", "r", stdin);
int __size__ = 256 << 20; // 256MB
char *__p__ = (char*)malloc(__size__) + __size__;
__asm__("movl %0, %%esp\n" :: "r"(__p__));
#endif //...........................................................................................................
fac[0] = 1;
for (int i = 1; i < maxn; i++) {
fac[i] = fac[i - 1] * i % mod;
}
invfac[maxn - 1] = pow(fac[maxn - 1], mod - 2, mod);
for (int i = maxn - 2; i >= 0; i--) {
invfac[i] = invfac[i + 1] * (i + 1) % mod;
}
cin >> n >> m >> stra >> strb >> strc >> strd;
solve();
swap(n, m);
swap(stra, strc);
swap(strb, strd);
solve();
if (cnt1(stra) + cnt1(strb) + cnt1(strc) + cnt1(strd) == 0) {
ans++;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Modern Painting |
User |
BSBandme |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
8176 Byte |
Status |
AC |
Exec Time |
15 ms |
Memory |
8656 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt |
All |
a01.txt, a02.txt, a03.txt, a04.txt, a05.txt, a06.txt, a07.txt, a08.txt, a09.txt, a10.txt, a11.txt, a12.txt, a13.txt, a14.txt, a15.txt, a16.txt, a17.txt, a18.txt, a19.txt, a20.txt, b01.txt, b02.txt, b03.txt, b04.txt, b05.txt, b06.txt, b07.txt, b08.txt, b09.txt, b10.txt, b11.txt, b12.txt, b13.txt, b14.txt, b15.txt, b16.txt, b17.txt, b18.txt, b19.txt, b20.txt, b21.txt, b22.txt, b23.txt, b24.txt, b25.txt, b26.txt, b27.txt, b28.txt, b29.txt, b30.txt, b31.txt, b32.txt, b33.txt, b34.txt, b35.txt, b36.txt, b37.txt, b38.txt, b39.txt, b40.txt, b41.txt, b42.txt, b43.txt, b44.txt, b45.txt, b46.txt, b47.txt, b48.txt, b49.txt, b50.txt, b51.txt, b52.txt, b53.txt, b54.txt, b55.txt, b56.txt, b57.txt, b58.txt, s01.txt, s02.txt, s03.txt, s04.txt, s05.txt, s06.txt, s07.txt |
Case Name |
Status |
Exec Time |
Memory |
a01.txt |
AC |
15 ms |
8656 KB |
a02.txt |
AC |
12 ms |
8448 KB |
a03.txt |
AC |
11 ms |
8320 KB |
a04.txt |
AC |
15 ms |
8656 KB |
a05.txt |
AC |
15 ms |
8656 KB |
a06.txt |
AC |
12 ms |
8400 KB |
a07.txt |
AC |
12 ms |
8400 KB |
a08.txt |
AC |
12 ms |
8400 KB |
a09.txt |
AC |
12 ms |
8400 KB |
a10.txt |
AC |
9 ms |
8064 KB |
a11.txt |
AC |
9 ms |
8064 KB |
a12.txt |
AC |
9 ms |
8064 KB |
a13.txt |
AC |
9 ms |
8064 KB |
a14.txt |
AC |
11 ms |
8320 KB |
a15.txt |
AC |
12 ms |
8320 KB |
a16.txt |
AC |
9 ms |
8064 KB |
a17.txt |
AC |
14 ms |
8528 KB |
a18.txt |
AC |
13 ms |
8576 KB |
a19.txt |
AC |
9 ms |
8064 KB |
a20.txt |
AC |
14 ms |
8576 KB |
b01.txt |
AC |
15 ms |
8656 KB |
b02.txt |
AC |
12 ms |
8448 KB |
b03.txt |
AC |
11 ms |
8320 KB |
b04.txt |
AC |
14 ms |
8656 KB |
b05.txt |
AC |
14 ms |
8656 KB |
b06.txt |
AC |
11 ms |
8400 KB |
b07.txt |
AC |
11 ms |
8400 KB |
b08.txt |
AC |
11 ms |
8400 KB |
b09.txt |
AC |
11 ms |
8400 KB |
b10.txt |
AC |
9 ms |
8064 KB |
b11.txt |
AC |
9 ms |
8064 KB |
b12.txt |
AC |
9 ms |
8064 KB |
b13.txt |
AC |
9 ms |
8064 KB |
b14.txt |
AC |
10 ms |
8320 KB |
b15.txt |
AC |
11 ms |
8320 KB |
b16.txt |
AC |
9 ms |
8064 KB |
b17.txt |
AC |
13 ms |
8528 KB |
b18.txt |
AC |
13 ms |
8576 KB |
b19.txt |
AC |
9 ms |
8064 KB |
b20.txt |
AC |
14 ms |
8576 KB |
b21.txt |
AC |
11 ms |
8656 KB |
b22.txt |
AC |
11 ms |
8656 KB |
b23.txt |
AC |
12 ms |
8656 KB |
b24.txt |
AC |
11 ms |
8656 KB |
b25.txt |
AC |
13 ms |
8656 KB |
b26.txt |
AC |
12 ms |
8656 KB |
b27.txt |
AC |
13 ms |
8656 KB |
b28.txt |
AC |
11 ms |
8656 KB |
b29.txt |
AC |
13 ms |
8656 KB |
b30.txt |
AC |
13 ms |
8656 KB |
b31.txt |
AC |
14 ms |
8656 KB |
b32.txt |
AC |
12 ms |
8656 KB |
b33.txt |
AC |
13 ms |
8656 KB |
b34.txt |
AC |
13 ms |
8656 KB |
b35.txt |
AC |
13 ms |
8656 KB |
b36.txt |
AC |
11 ms |
8656 KB |
b37.txt |
AC |
11 ms |
8656 KB |
b38.txt |
AC |
12 ms |
8656 KB |
b39.txt |
AC |
12 ms |
8656 KB |
b40.txt |
AC |
12 ms |
8656 KB |
b41.txt |
AC |
13 ms |
8656 KB |
b42.txt |
AC |
12 ms |
8656 KB |
b43.txt |
AC |
13 ms |
8656 KB |
b44.txt |
AC |
12 ms |
8656 KB |
b45.txt |
AC |
12 ms |
8656 KB |
b46.txt |
AC |
12 ms |
8656 KB |
b47.txt |
AC |
12 ms |
8656 KB |
b48.txt |
AC |
11 ms |
8656 KB |
b49.txt |
AC |
13 ms |
8656 KB |
b50.txt |
AC |
14 ms |
8656 KB |
b51.txt |
AC |
15 ms |
8656 KB |
b52.txt |
AC |
11 ms |
8656 KB |
b53.txt |
AC |
9 ms |
8064 KB |
b54.txt |
AC |
9 ms |
8064 KB |
b55.txt |
AC |
9 ms |
8064 KB |
b56.txt |
AC |
9 ms |
8064 KB |
b57.txt |
AC |
9 ms |
8064 KB |
b58.txt |
AC |
9 ms |
8064 KB |
s01.txt |
AC |
9 ms |
8064 KB |
s02.txt |
AC |
9 ms |
8064 KB |
s03.txt |
AC |
9 ms |
8064 KB |
s04.txt |
AC |
9 ms |
8064 KB |
s05.txt |
AC |
9 ms |
8064 KB |
s06.txt |
AC |
9 ms |
8064 KB |
s07.txt |
AC |
9 ms |
8064 KB |