列表

详情

NC20894. 无畏死灵术士莉莲娜与锁链面纱

描述

「你若发现自己在遗忘边界摇摇欲坠，我的双手很乐意推上最后一把。」             ——莉莲娜维斯


       莉莲娜维斯受恶魔柯索菲的要求来到欧娜卡寻找远古巨魔文明遗留下来的强大神器——锁链面纱。她冲破重重阻碍，来到欧娜卡的寺庙，企图得到锁链面纱，却遇到了一些难题。
       锁链面纱被一些机关巧妙的保护起来。这个机关是由 n 块大小不一的石头组成的，我们可以将它们按照从小到大的顺序编号为 。莉莲娜的任务是把这些石头从小到大地排好序。每一次，莉莲娜可以挑选其中一块石头为其注入能量，之后其他所有的石头中，比这块注入能量的石头小的石头会保持相对顺序不变地移动到它的左边，其余的保持相对顺序不变地移动到右边。举个例子，一开始有石头序列为 {3, 2, 1, 5, 6, 4}，假如莉莲娜选择石头 4，那么石头序列会变成 {3, 2, 1, 4, 5, 6}，原因是其中的 1, 2, 3 号石头按需留在 4 号石头左边，而 5, 6 号石头按序移动到 4 号石头右边；假如莉莲娜选择石头 2，那么石头序列会变成 {1, 2, 3, 5, 6, 4} 。
       莉莲娜不想花费太多精力在破解这个小小的机关上，所以她召唤了一只灵俑来帮她。灵俑十分愚蠢，每次只会在 n 块石头中等概率随机一个注入能量。莉莲娜想请你告诉她，这只灵俑能成功解开机关的期望注能次数是多少？答案对 998244353 取模。
       可以证明答案能被表示为 的形式 ，其中 a 和 b 互质。输出整数 x 使得 且 0 ≤ x < 998244353 。可以证明这样的整数 x 是唯一的。

输入描述

从标准输入中读入。
第一行一个正整数 n 。
第二行 n 个正整数表示一个 1 到 n 的排列。

输出描述

输出到标准输出。
一行，表示答案。对 998244353 取模。

示例1

输入: 

3
2 3 1

输出: 

499122178

说明:

序列初始为 {2, 3, 1} 。
- 假设第一次选择了 1，那么序列变为 {1, 2, 3}，排序完成。
- 假设第一次选择了 2，那么序列变为 {1, 2, 3}，排序完成。
- 假设第一次选择了 3，那么序列变为 {2, 1, 3}，排序未完成。
    = 假设第二次选择了 1 或 2，那么序列变为 {1, 2, 3}，排序完成。
    = 假设第二次选择了 3，那么序列不变。
    ……
根据期望的定义以及无穷级数的计算可以得到答案为 \displaystyle \frac{3}{2}, 对 998244353 取模后结果为 499122178 。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 139ms, 内存消耗: 4464K, 提交时间: 2020-08-07 00:33:47 

#include<bits/stdc++.h>
using namespace std;
 
const long long mod=998244353;
int DP[1100005]={0};
int main()
{
    int i,j,k,n,V[25],inv[25];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&j),V[j]=i;
    inv[1]=1;
    for(i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(i=0;i<(1<<n);i++)
        for(j=1;j<n;j++)
        {
            if(((1<<(j-1))&i)||((1<<j)&i))continue;
			if(V[j]>V[j+1])DP[i]=n;
        }
    for(i=(1<<n)-1;i>=0;i--)
    {
		for(j=k=0;j<n;j++)
        {
            if(i&(1<<j))k++;
            else DP[i]=(DP[i]+DP[i|1<<j])%mod;
        }
        DP[i]=(long long)DP[i]*inv[n-k]%mod;
    }
    printf("%d\n",DP[0]);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 115ms, 内存消耗: 4440K, 提交时间: 2020-08-06 19:20:53 

#include<bits/stdc++.h>
using namespace std;

const long long mod=998244353;
int DP[1100005]={0};
int main()
{
	int i,j,k,n,V[25],inv[25];
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&j),V[j]=i;
	inv[1]=1;
	for(i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(i=0;i<(1<<n);i++)
		for(k=-1,j=0;j<n;j++)
		{
			if(i&(1<<j))k=-1;
			else
			{
				if(k>V[j+1])DP[i]=1,j=n-1;
				k=V[j+1];
			}
		}
	for(i=(1<<n)-1;i>=0;i--)
	{
		if(DP[i])DP[i]=n;
		for(j=k=0;j<n;j++)
		{
			if(i&(1<<j))k++;
			else DP[i]=(DP[i]+DP[i|1<<j])%mod;
		}
		DP[i]=(long long)DP[i]*inv[n-k]%mod;
	}
	printf("%d\n",DP[0]);
    return 0;
}

上一题

© 2024 nowcoder.com