题意:给定一个排列 \(p\),求满足下列条件的 \(a\) 数组的数量。
-
\(1\le a_i\le m\)。
-
\(a\) 数组的字典序小于 \(\{a_{p_1},a_{p_2},\cdots,a_{p_n}\}\)。
题解:
由于每一个 \(a < a_p\) 的方案都可以反过来变成 \(a > a_p\),那么只需要计算 \(a = a_p\) 的方案数即可。
如果 \(a = a_p\),那么 \(a_i = a_{p_i}\),\(i\) 和 \(p_i\) 之间连一条无向边,求连通块的个数为 \(lth\),那么 \(a < a_p\) 的方案数是 \((m^n-m^{lth})/2\)。
#include <bits/stdc++.h>
using namespace std;
int ksm(int a, int b, int c)
{
if (!b)
return 1;
int ans = ksm(a, b >> 1, c);
ans = 1ll * ans * ans % c;
if (b & 1)
ans = 1ll * ans * a % c;
return ans;
}
const int N = 2e5 + 10;
const int mod = 998244353;
int p[N];
vector <int> z[N];
bool vis[N];
void dfs(int u)
{
vis[u] = true;
for (auto &v : z[u])
if (!vis[v])
dfs(v);
}
signed main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> p[i];
for (int i = 1; i <= n; i ++)
z[i].push_back(p[i]);
int cnt = 0;
for (int i = 1; i <= n; i ++)
if (!vis[i])
{
cnt ++;
dfs(i);
}
int p = ksm(m, n, mod) - ksm(m, cnt, mod);
p %= mod;
p += mod;
p %= mod;
p = 1ll * p * ksm(2, mod - 2, mod) % mod;
cout << p << '\n';
return 0;
}
原文地址:http://www.cnblogs.com/BaiduFirstSearch/p/16817899.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性