テキトーなメモ帳

テキトーなメモ帳

AOJ:0271 Izua Dictionary

わけがわからなかったので、いろんな方のコードを読んで研究(?)した結果、


辞書順での位置を探したい単語の文字を最右端から左へむかって走査していって、
[現在走査している位置よりも右側にあり、かつ数字が小さいものの個数] * [現在走査している位置よりも右側にある数字の個数の階乗]
を順々に足し合わせていけばよいらしい。


という結論になりました。
(ちなみに、「現在走査している位置よりも右側にあり、かつ数字が小さいものの個数」はBinaryIndexedTreeを使って保存しておけばいい。)


では、例として3412の辞書順での位置をだしてみましょう。
2->1->4->3の順で走査していくとして、


2は
「現在走査している位置よりも右側にあり、かつ数字が小さいものの個数」は0
「現在走査している位置よりも右側にある数字の個数の階乗」は0!
0 * 0! = 0


1は
「現在走査している位置よりも右側にあり、かつ数字が小さいものの個数」は0
「現在走査している位置よりも右側にある数字の個数の階乗」は1!
0 * 1! = 0


4は
「現在走査している位置よりも右側にあり、かつ数字が小さいものの個数」は2
「現在走査している位置よりも右側にある数字の個数の階乗」は2!
2 * 2! = 4(並び‘24’と’14’で2つ分の2!の組み合わせがあるという意味)


3は
「現在走査している位置よりも右側にあり、かつ数字が小さいものの個数」は2
「現在走査している位置よりも右側にある数字の個数の階乗」は3!
2 * 3! = 12(並び‘234’と’134’で2つ分の3!の組み合わせがあるという意味)


よって最終的な答えは
4 + 12 = 16
となります


図示するとこんな感じ

#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

const static ll MOD = 1000000007;

class BinaryIndexedTree {
private:
  int* bit;
  int n;
public:
  BinaryIndexedTree(int _size){
    bit = new int[_size];
    n = _size;
    fill(bit,bit+_size,0);
  }
  int sum(int i){
    int s = 0;
    while(i > 0){
      s += bit[i];
      i -= i & -i;
    }
    return s;
  }
  
  void add(int i, int x){
    while(i <= n){
      bit[i] += x;
      i += i & -i;
    }
  }
};

int main(){
  int N,R;
  ll dp[100001];
  ll target[100001];

  while(~scanf("%d %d",&N,&R)){
    if(N == 0) break;

    memset(dp,0,sizeof(dp));
    dp[0] = 1;

    for(int i=1;i<=N;i++){
      target[i] = i;
      // 4
      // v v v v
      //  1 2 3
      dp[i] = dp[i-1] * i % MOD;
    }
    for(int r = 0; r< R;r++){
      int from_idx;
      int to_idx;
      scanf("%d %d",&from_idx,&to_idx);
      swap(target[from_idx],target[to_idx]);
    }

    ll res = 0;
    BinaryIndexedTree BIT(100001);
    for(int i=N,j=0;i>=1;i--,j++){
      res += ((dp[j] % MOD) * (BIT.sum(target[i] - 1) % MOD) % MOD);
      res %= MOD;
      BIT.add(target[i],1);
    }
    printf("%lld\n",res);
  }
}