답안 #534711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534711 2022-03-08T15:44:18 Z cig32 Automobil (COCI17_automobil) C++17
55 / 100
11 ms 2124 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 n, m, k;
  cin >> n >> m >> k;
  map<int, int> 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;
  }
  int tot = n*m;
  tot %= MOD;
  tot *= (n*m + 1);
  tot %= MOD;
  tot *= inv(2);
  tot %= MOD;
  for(auto x: row) {
    int st = (x.first - 1) * m + 1;
    int en = (x.first - 1) * m + m;
    int 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) {
    int st = x.first;
    int en = (n - 1) * m + x.first;
    int 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) {
      int uwu = (x.first - 1) * m + y.first;
      uwu %= MOD;
      tot = (tot + uwu) % MOD;
      int 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 << 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);
} 
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1868 KB Output is correct
2 Correct 4 ms 1868 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Correct 3 ms 1868 KB Output is correct
5 Correct 4 ms 1892 KB Output is correct
6 Correct 4 ms 1868 KB Output is correct
7 Correct 5 ms 1888 KB Output is correct
8 Correct 4 ms 1868 KB Output is correct
9 Correct 4 ms 1868 KB Output is correct
10 Correct 5 ms 1868 KB Output is correct
11 Incorrect 5 ms 1888 KB Output isn't correct
12 Incorrect 9 ms 2124 KB Output isn't correct
13 Correct 4 ms 1868 KB Output is correct
14 Incorrect 3 ms 1868 KB Output isn't correct
15 Incorrect 6 ms 1868 KB Output isn't correct
16 Incorrect 8 ms 1996 KB Output isn't correct
17 Incorrect 8 ms 1996 KB Output isn't correct
18 Incorrect 9 ms 1996 KB Output isn't correct
19 Incorrect 9 ms 1952 KB Output isn't correct
20 Incorrect 11 ms 2024 KB Output isn't correct