首页 > 其他分享 >POI2008PER-Permutation

POI2008PER-Permutation

时间:2024-04-15 19:47:05浏览次数:31  
标签:pr int res sum POI2008PER while Permutation ph

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

相关文章

  • [CF1718D] Permutation for Burenka 瞎扯
    尝试回到1,2月份的文风。感觉,自己思考的时候最好不要乱走,模拟一下考场上的氛围和紧张感,让自己保持专注。但是当你已经了解了这个问题的全貌后,随机游走一会,仔细观察问题,梳理思路,感觉收获会比较大。所以看起来我不擅长自己想题,比较擅长马后炮。[CF1718D]PermutationforBur......
  • SP64 PERMUT1 - Permutations 题解
    题目传送门前置知识动态规划基础解法设\(f_{i,j}\)表示\(1\simi\)的全排列中存在\(j\)个逆序对的方案数,状态转移方程为\(f_{i,j}=\sum\limits_{k=j-\min(i-1,j)}^{j}f_{i-1,k}=\sum\limits_{k=0}^{j}f_{i-1,k}-\sum\limits_{k=0}^{j-\min(i-1,j)-1}f_{i-1,k}\)。需......
  • 「CF1677D」Tokitsukaze and Permutations的题解
    「CF1677D」TokitsukazeandPermutations首先,若\(v\)的后\(k\)个数中有一个\(>0\),或有\(v_i>i-1(i\in[1,n])\),则无解。我们发现,每次对\(p\)进行了一次操作后,\(v\)也一定会对应的进行一次变化,所以统计\(p\)的个数就相当于统计\(v\)的个数。我们对于每一次冒泡排序......
  • CodeForces 1936E Yet Yet Another Permutation Problem
    洛谷传送门CF传送门首先设\(a_i=\max\limits_{j=1}^ip_j\),\(b_i=\max\limits_{j=1}^iq_j\)。直接容斥,钦定有多少值不同的\(a_i\)使得\(a_i=b_i\)。然后再把钦定的每种值转化成每种值第一次使得\(a_i=b_i\)的位置\(i\)。也就是说我们现在要钦定一些位置,......
  • P9632 [ICPC2020 Nanjing R] K Co-prime Permutation
    原题链接题解我一开始也很困惑,然后我想要不数据范围小一点我构造看看当\(n=5\)时\(k=0\)可不可以\(k=1\)可不可以\(k=2\)可不可以然后根据直觉,\(gcd(a,a+1)\)始终为一,且一和任何数的最大公约数都为一,自己和自己的最大公约数还是自己,所以萌生了以下想法把一后面......
  • AT_abc283_f [ABC283F] Permutation Distance 题解
    分析分类讨论。对\(|p_i-p_j|+|i-j|\)分类讨论,有:\((p_i+i)-(p_j+j)\),\(p_i>p_j\landi>j\)。\(-(p_i-i)+(p_j-j)\),\(p_i<p_j\landi>j\)。\((p_i-i)-(p_j-j)\),\(p_i>p_j\landi<j\)。\(-(p_i+i)+(p_j+j)\),\(p_i<p_j\landi<j......
  • ABC134F Permutation Oddness
    [ABC134F]PermutationOddness好题,牛牛的一个套路——\(\textsfH\)\(\textsf{anghang}\)写起来简单,想起来难的一个东西,难点主要是在状态设置上我们可以把\(1\simN\)拆点,于是原题相当于求一个二分图的完美匹配,并使其怪异度为\(k\)我们考虑设置\(f_{i,j,k}\)......
  • [ARC140F] ABS Permutation (Count ver.) 题解
    洛谷题面传送门AT题面传送门发现不太好直接求,考虑将\(P\)映射到\(P^{-1}\)上,这样题目中的条件就变成了\(|P_i-P_{i+M}|=1\)。因此我们可以对模\(M\)的每个剩余系做\(M=1\)的情况,然后最后快速幂合并。考虑\(M=1\)的情况怎么做。记\(f_i\)表示\(K=i\)的方案数,......
  • Gym 104855E Perfect Permutation
    考虑最后对于每个\(i\)是选\(a_i,b_i,c_i\)之中哪一个的序列。通过观察能发现序列去掉\(b\)后满足开头为\(c\)末尾为\(a\)这个序列就是合法的,同时整个序列都为\(b\)也是合法的。首先如果是个合法序列,对于去掉\(b\)后的开头,其余不是\(b\)的下标肯定比其大,所以......
  • E. Klever Permutation
    E.KleverPermutationYouaregiventwointegers$n$and$k$($k\len$),where$k$iseven.Apermutationoflength$n$isanarrayconsistingof$n$distinctintegersfrom$1$to$n$inanyorder.Forexample,$[2,3,1,5,4]$isapermutation,but$[1,2,......