AOJ 0271: Izua Dictionary

解説

文字列をsとして愚直にシミュレーションしていくと、sを適当に入れ替えたときのi番目(1 <= i <= n)の文字の位置を求めるのに、i番目までに使った文字が影響される。よって最初にBITで[1, n]に1を加えておき、s[i]の場所ごとにiを0にしていくことで、sum(i)でi番目の文字の位置を求めることができる。（日本語難しすぎ）
割とゴリ押しな感じあふれてる。

ソースコード

めっちゃ汚い…

typedef long long i64;
const i64 MOD = 1000000007;
const int MAX_N = 100002;

struct BinaryIndexedTree {
	int data[MAX_N];

	BinaryIndexedTree() {
		memset(data, 0, sizeof data);
	}

	// [1, n]
	i64 sum(i64 i) {
		i64 ret = 0;
		for(; i > 0; i -= i & -i) {
			ret += data[i];
		}
		return ret;
	}

	void add(i64 i, i64 x) {
		for(; i < MAX_N; i += i & -i) {
			data[i] += x;
		}
	}
};

int main() {
	int pair[MAX_N];
	i64 ans;
	i64 fact[MAX_N];
	
	fact[0] = 1;
	for(int i = 1; i < MAX_N; i++) {
		fact[i] = i * fact[i - 1];
		fact[i] %= MOD;
	}

	int n, r;
	while(cin >> n, n) {
		cin >> r;

		ans = 0;
		BinaryIndexedTree b;

		for(int i = 0; i < MAX_N; i++) {
			b.add(i + 1, 1);
			pair[i] = i;
		}

		for(int i = 0, a, b; i < r; i++) {
			cin >> a >> b;
			swap(pair[a-1], pair[b-1]);
		}

		for(int i = 0; i < n; i++) {
			i64 x = b.sum(pair[i] + 1) - 1;
			b.add(pair[i] + 1, -1);
			ans += x * fact[n - i - 1];
			ans %= MOD;
		}

		cout << ans << endl;
	}
}