POI #Year2008 #数学 #康拓展开 #逆元
如果是一个排列,根据康拓展开,答案为
\[\sum\limits_{i=1}^nsum_{i}\times (n-i)! \]其中
\[sum_{i}=\sum\limits_{j=i+1}^n[a_i>a_j] \]那么再加入了重复的数字之后,答案变为
\[ \sum\limits_{i=1}^n \frac{sum_i\times (n-i)!}{\prod\limits_{j\in s_i} cnt_j} \]其中 \(s_i=\{a_j|j\in [i,n]\}\)
考虑怎么再非质数模数下计算这个东西,可以先对模数质因子分解,然后对于每个质因子统计个数,对于非质因子,即存在逆元可以直接算
// Author: xiaruize
const int N = 3e5 + 10;
int n, m;
int a[N];
int sum[N];
int pr[N], tot, cnt[N];
int ph;
int inv[N];
void init(int x)
{
rep(i, 2, x)
{
if (i * i > x)
break;
if (x % i == 0)
{
pr[++tot] = i;
ph = ph / i * (i - 1);
while (x % i == 0)
x /= i;
}
}
if (x != 1)
{
pr[++tot] = x;
ph = ph / x * (x - 1);
}
}
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int cur = 1, res = 0;
void mul(int x, int &t)
{
rep(i, 1, tot)
{
while (x % pr[i] == 0)
{
x /= pr[i];
cnt[i]++;
}
}
t = t * x % m;
}
void divi(int x, int &t)
{
rep(i, 1, tot)
{
while (x % pr[i] == 0)
{
x /= pr[i];
cnt[i]--;
}
}
t = t * qpow(x, ph - 1) % m;
}
struct BIT
{
int tr[N];
void add(int x, int v)
{
while (x <= 3e5)
{
tr[x] += v;
x += x & -x;
}
}
int sum(int x)
{
int res = 0;
while (x)
{
res += tr[x];
x -= x & -x;
}
return res;
}
} tr;
int get()
{
int res = cur % m;
rep(i, 1, tot) res = res * qpow(pr[i], cnt[i]) % m;
return res;
}
void solve()
{
cin >> n >> m;
ph = m;
init(m);
rep(i, 1, n) cin >> a[i];
sum[a[n]]++;
tr.add(a[n], 1);
per(i, n - 1, 1)
{
int w = tr.sum(a[i] - 1);
debug(i);
mul(n - i, cur);
debug(i);
tr.add(a[i], 1);
sum[a[i]]++;
divi(sum[a[i]], cur);
if (!w)
continue;
mul(w, cur);
res = (res + get()) % m;
divi(w, cur);
}
cout << (res + 1) % m << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed
main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:"
<< (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB"
<< endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms"
<< endl;
#endif
return 0;
}
标签:pr,int,res,sum,POI2008PER,while,Permutation,ph
From: https://www.cnblogs.com/xiaruize/p/18136780