Instantly share code, notes, and snippets.

koosaga/fb17r3a.cpp Created Jan 29, 2017

FBHC17 R3 Solution
 #include using namespace std; typedef long long lint; typedef pair pi; const int mod = 1e9 + 7; int rev[1005], sfx[1005]; char str[1005]; int n; void solve(){ scanf("%d",&n); for(int i=0; i 'Z'){ puts("-1"); return; } } } cout << str << endl; int arr[1005]; for(int i=0; i
 #include using namespace std; typedef long long lint; typedef pair pi; const int mod = 1e9 + 7; lint fact[4000005], invf[4000005]; lint bino(int x, int y){ return fact[x] * (invf[y] * invf[x-y] % mod) % mod; } int n, a[2000005], b[2000005]; int chk1[2000005], chk2[2000005]; int hl[2000005], hr[2000005]; vector v; int solve(int s, int e, int *a){ if((e - s + 1) % 2 != 0) return -1; int cnt = 0; for(int i=s; i<=e; i+=2){ if(a[i] != a[i+1]){ if(i + 3 <= e && a[i] == a[i+2] && a[i+1] == a[i+3]){ cnt++; i += 2; continue; } else return -1; } cnt++; } return cnt; } lint solve(int sx, int ex, int sy, int ey){ while(chk1[sx] && sx <= ex) sx++; while(chk1[ex] && sx <= ex) ex--; while(chk2[sy] && sy <= ey) sy++; while(chk2[ey] && sy <= ey) ey--; int p1 = solve(sx, ex, a); int p2 = solve(sy, ey, b); if(p1 == -1 || p2 == -1) return 0; return bino(p1 + p2, p2); } void solve(){ if(n == 1){ puts("1"); return; } for(int i=1; i<=n; i++){ hl[a[i]] = i; hr[b[i]] = i; } for(int i=1; i<=n; i++){ if(hl[i] && hr[i]){ v.push_back(pi(hl[i], hr[i])); } } sort(v.begin(), v.end()); lint ret = 1; for(int i=1; i v[i].second){ if(v[i].first == v[i-1].first + 1 && v[i-1].second == v[i].second + 1){ swap(v[i].second, v[i-1].second); ret *= 2; ret %= mod; continue; } puts("0"); return; } } for(int i=0; i 1 && a[p1-1] == a[p1+1]) l = 1; if(p2 < n && p2 > 1 && b[p2-1] == b[p2+1]) r = 1; if(l && r){ puts("0"); return; } if(l) chk1[p1-1] = chk1[p1+1] = 1; if(r) chk2[p2-1] = chk2[p2+1] = 1; if(l || r) ret = (ret * 2) % mod; } if(v.empty()){ ret *= solve(1, n, 1, n); ret %= mod; } else{ ret *= solve(1, v[0].first - 1, 1, v[0].second - 1); ret %= mod; ret *= solve(v.back().first + 1, n, v.back().second + 1, n); ret %= mod; for(int i=1; i>= 1; } return ret % mod; } void input(){ v.clear(); memset(hl, 0, sizeof(hl)); memset(hr, 0, sizeof(hr)); memset(chk1, 0, sizeof(chk1)); memset(chk2, 0, sizeof(chk2)); cin >> n; int ka, kb; cin >> a[1] >> ka; int p = 2; for(int i=0; i> b[1] >> ka; p = 2; for(int i=0; i
 #include using namespace std; typedef long long lint; typedef pair pi; const int mod = 1e9 + 7; void dijkstra(); int n; lint a[2000005], b[2000005], l; int c[1000005]; struct bit{ int tree[1000005]; void clear(){ memset(tree, 0, sizeof(tree)); } void add(int x, lint v){ v %= mod; v += mod; v %= mod; x++; while(x <= n){ tree[x] += v; tree[x] %= mod; x += x & -x; } } int query(int x){ x++; int ret = 0; while(x){ ret += tree[x]; ret %= mod; x -= x & -x; } return ret; } int query(int s, int e){ return (query(e) - query(s-1) + mod) % mod; } }cnt1, sum1, sum2, cnt2, sum3, sum4; int op1[1000005], op2[1000005]; void solve(){ dijkstra(); lint ret = 0; for(int i=1; i<=n; i++){ ret += b[i]; ret %= mod; } for(int i=1; i<=n; i++){ l += a[i]; a[i] += a[i-1]; } for(int i=n; i; i--){ a[i] = a[i-1]; } vector fac1, fac2; for(int i=1; i<=n; i++){ fac1.push_back(a[i] - b[i]); fac2.push_back(l - a[i] - b[i]); } sort(fac1.begin(), fac1.end()); sort(fac2.begin(), fac2.end()); fac1.resize(unique(fac1.begin(), fac1.end()) - fac1.begin()); fac2.resize(unique(fac2.begin(), fac2.end()) - fac2.begin()); for(int i=1; i<=n; i++){ op1[i] = lower_bound(fac1.begin(), fac1.end(), a[i] - b[i]) - fac1.begin(); op2[i] = lower_bound(fac2.begin(), fac2.end(), l - a[i] - b[i]) - fac2.begin(); } cnt1.clear(); sum1.clear(); sum2.clear(); cnt2.clear(); sum3.clear(); sum4.clear(); int e = 1; for(int i=1; i<=n; i++){ cnt2.add(op2[i], 1); sum3.add(op2[i], b[i]); sum4.add(op2[i], (l - a[i]) % mod); } for(int i=1; i<=n; i++){ while(e <= n && a[e] - a[i] < l - a[e] + a[i]){ cnt1.add(op1[e], 1); sum1.add(op1[e], b[e]); sum2.add(op1[e], a[e] % mod); cnt2.add(op2[e], mod-1); sum3.add(op2[e], mod-b[e]); sum4.add(op2[e], mod - (l - a[e]) % mod); e++; } cnt1.add(op1[i], mod-1); sum1.add(op1[i], mod-b[i]); sum2.add(op1[i], mod-a[i] % mod); int k1 = lower_bound(fac1.begin(), fac1.end(), b[i] + a[i] + 1) - fac1.begin(); ret += 1ll * b[i] * cnt1.query(k1, n-1) % mod + sum1.query(k1, n-1); ret %= mod; ret += sum2.query(0, k1-1) - 1ll * (a[i] % mod) * cnt1.query(0, k1-1) % mod + mod; ret %= mod; int k2 = lower_bound(fac2.begin(), fac2.end(), b[i] - a[i] + 1) - fac2.begin(); ret += 1ll * (a[i] % mod) * cnt2.query(0, k2-1) % mod + sum4.query(0, k2-1); ret %= mod; ret += 1ll * b[i] * cnt2.query(k2, n-1) % mod + sum3.query(k2, n-1); ret %= mod; /* for(int j=i+1; j, greater> pq; pq.push(pi(0, n+1)); memset(dis, 0x3f, sizeof(dis)); dis[n+1] = 0; while(!pq.empty()){ auto x = pq.top(); pq.pop(); if(dis[x.second] != x.first) continue; if(x.second == n+1){ for(int i=1; i<=n; i++){ if(dis[i] > dis[x.second] + b[i]){ dis[i] = dis[x.second] + b[i]; pq.push(pi(dis[i], i)); } } } else{ int i = x.second; if(i == 1){ if(dis[n] > dis[1] + a[n]){ dis[n] = dis[1] + a[n]; pq.push(pi(dis[n], n)); } } else{ if(dis[i-1] > dis[i] + a[i-1]){ dis[i-1] = dis[i] + a[i-1]; pq.push(pi(dis[i-1], i-1)); } } if(i == n){ if(dis[1] > dis[n] + a[n]){ dis[1] = dis[n] + a[n]; pq.push(pi(dis[1], 1)); } } else{ if(dis[i+1] > dis[i] + a[i]){ dis[i+1] = dis[i] + a[i]; pq.push(pi(dis[i+1], i+1)); } } } } for(int i=1; i<=n; i++) b[i] = dis[i]; } void input(){ int p, q, r, s; cin >> n; l = 0; cin >> a[1] >> p >> q >> r >> s; for(int i=2; i<=n; i++){ a[i] = (1ll * p * a[i-1] + q) % r + s; } cin >> b[1] >> p >> q >> r >> s; for(int i=2; i<=n; i++){ b[i] = (1ll * p * b[i-1] + q) % r + s; } } int main(){ int t; scanf("%d",&t); for(int i=1; i<=t; i++){ printf("Case #%d: ", i); input(); solve(); } }
to join this conversation on GitHub. Already have an account? Sign in to comment