E1.1.4. 捷径？歧路？的答案

#include<bits/stdc++.h>

typedef long long lld;

const int N = 1e5 + 9, mod = 1e9 + 7;

int n, m, a[N], frac[N], tr[N];

inline int lowbit(int x) 

{

return x & (-x); 

} 

void insert(int x) 

{

while (x <= n) 
{
	++tr[x]; x += lowbit(x);
}


} 

int query(int x) 

{ 

int s = 0; 
while (x) 
{ 
s += tr[x]; 
x -= lowbit(x); 
} 
return s;

}

int cantor() 

{ 

	memset(tr, 0, sizeof tr);
	int s = 0;
	for (int i = 0; i < n; ++i) 
	{
	int t = (n - a[i]) - (i - query(a[i]));
	insert(a[i]);
	s = (s + (lld)t * frac[n - 1 - i]) % mod;
	}
	return (s + 1) % mod;

}

int main() 

{ 

	scanf("%d%d", &n, &m);
	frac[0] = 1;
	for (int i = 1; i < n; ++i) 
	frac[i] = (lld)frac[i - 1] * i % mod;
	while (m--) 
	{
		for (int i = 0; i < n; ++i) scanf("%d", a + i);
		printf("%d\n", cantor());
	}

}