oj.uz

답안 #534715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534715 2022-03-08T15:59:28 Z cig32 Automobil (COCI17_automobil) C++17
100 / 100
 18 ms 2024 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}

void solve(int tc) {
  int a, b, c;
  cin >> a >> b >> c;
  __int128 n, m, k;
  n = a, m = b, k = c;
  map<__int128, __int128> row, col;
  map<int, bool> er, ec;
  for(int i=0; i<k; i++) {
    char c; cin >> c;
    int x, y; cin >> x >> y;
    if(c == 'R') row[x] = (er[x] ? (y * row[x]) % MOD : y);
    else col[x] = (ec[x] ? (y * col[x]) % MOD : y);
    if(c == 'R') er[x] = 1;
    else ec[x] = 1;
  }
  __int128 tot = n*m;
  tot %= MOD;
  tot *= (n*m + 1);
  tot %= MOD;
  tot *= inv(2);
  tot %= MOD;
  for(auto x: row) {
    __int128 st = (x.first - 1) * m + 1;
    __int128 en = (x.first - 1) * m + m;
    __int128 pot = (st + en) * m / 2;
    pot %= MOD;
    tot = (tot + MOD - pot) % MOD;

    pot *= x.second;
    pot %= MOD;
    tot = (tot + pot) % MOD;
  }
  for(auto x: col) {
    __int128 st = x.first;
    __int128 en = (n - 1) * m + x.first;
    __int128 pot = (st + en) * n / 2;
    pot %= MOD;
    tot = (tot + MOD - pot) % MOD;

    pot *= x.second;
    pot %= MOD;
    tot = (tot + pot) % MOD;
  }
  for(auto x: row) {
    for(auto y: col) {
      __int128 uwu = (x.first - 1) * m + y.first;
      uwu %= MOD;
      tot = (tot + uwu) % MOD;
      __int128 old = uwu;
      uwu *= x.second;
      uwu %= MOD;
      tot = (tot + MOD - uwu) % MOD;
      uwu = old;

      uwu *= y.second;
      uwu %= MOD;
      tot = (tot + MOD - uwu) % MOD;

      uwu *= x.second;
      uwu %= MOD;
      tot = (tot + uwu) % MOD;
    }
  }
  cout << (long long)tot << '\n';
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 6 ms 1868 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 5 ms 1868 KB Output is correct
5 Correct 6 ms 1868 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 9 ms 1868 KB Output is correct
8 Correct 5 ms 1996 KB Output is correct
9 Correct 6 ms 1868 KB Output is correct
10 Correct 9 ms 1868 KB Output is correct
11 Correct 8 ms 1868 KB Output is correct
12 Correct 17 ms 1996 KB Output is correct
13 Correct 6 ms 1940 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 12 ms 1992 KB Output is correct
16 Correct 18 ms 1996 KB Output is correct
17 Correct 17 ms 1996 KB Output is correct
18 Correct 18 ms 2000 KB Output is correct
19 Correct 18 ms 2024 KB Output is correct
20 Correct 18 ms 2016 KB Output is correct