[ICPC] 백준 30484 - Inversions

https://www.acmicpc.net/problem/30484

힌트

각 인덱스에서 알파벳이 몇 개 나오는지 $O(1)$에 계산할 수 있는 방법이 있다.

풀이

문제에서는 자기보다 뒤에 있는 문자에서 사전 순으로 작은 녀석들의 횟수를 찾아야 한다.

 

우리는 이를 쉽게 계산하기 위해 각 알파벳 등장 횟수를 suffix 누적합 $suff$로 계산해 저장할 것이다.

 

그러면 $N - 1$번 만큼의 반복에 대해 사전순으로 작은 알파벳 횟수 $suff[0][character]$를 계산할 수 있고 최초 반복에서는 인덱스 $i$에 대해 $suff[i][character]$를 더하면 최종 답을 구할 수 있다.

 

정답 코드 - C++

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
 
using namespace std;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
 
string pat;
ll n;
constexpr int MXS = 1e5+2;
constexpr int MOD = 1e9 + 7;
int suff[MXS][26];
int mp[26];
int pref_mp[26];
 
void solve()
{
  cin >> pat >> n;
  n %= MOD;
  for (int c : pat)
  {
    ++mp[c - 'a'];
  }
 
  pref_mp[0] = mp[0];
  for (int i = 1; i < 26; i++)
  {
    pref_mp[i] = mp[i] + pref_mp[i - 1];
  }
 
  int sz = size(pat);
  for (int i = sz - 1; i >= 0; i--)
  {
    suff[i][pat[i] - 'a']++;
    for (int j = 0; j < 26; j++)
    {
      suff[i][j] += suff[i + 1][j];
    }
  }
 
  ll ans = 0;
  for (int c : pat)
  {
    if (c == 'a' or c == '$') continue;
    ll counting = (1LL + (n - 1)) * (n - 1) / 2 % MOD;
    ans += counting * pref_mp[c - 'a' - 1] % MOD;
    ans %= MOD;
  }
 
  for (int i = 0; i < sz; i++)
  {
    ll val = 0;
    for (int j = 'a'; j < pat[i]; j++)
    {
      val += suff[i][j - 'a'];
    }
    val *= n;
    val %= MOD;
    ans += val;
    ans %= MOD;
  }
 
  while (ans < 0) ans += MOD;
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}