列表

详情

NC222112. AC自动机fail树dfs序建可持久化线段树

描述

whaleshark在学习AC自动机的时候，看到了一副经典对联：

上联：AC自动机fail树dfs序建可持久化线段树

下联：后缀自动机next指针dag图上跑SG函数

在感慨AC自动机神奇的同时，whaleshark也想利用AC自动机AC！于是他决定自己也要造一台AC自动机！

经过不懈的努力，AC自动机终于被造好了！这台AC自动机的能够输出上联，也就是“AC自动机fail树dfs序建可持久化线段树”这一字符串。

可是机器突然出现了故障，输出的时候每个字符有一定的几率无法被输出！

他研究了一会，发现AC自动机输出的时候，其中的每个字符无法被输出的几率都是一样的！

由于whaleshark是初学者，他认为当一个字符串含有子序列“AC”的时候，这个字符串就会被AC。

子序列是指去除字符串中的某些字符，且不改变其他字符的相对位置而形成的新序列

例："ACE"是"ABCDE"的子序列，"AEC"则不是。

现在已知每个字符无法被输出的概率，whaleshark想知道这台AC自动机输出一次被AC的概率。

答案对998244353取模。

输入描述

输入第一行包括一个整数T(T<=1e5)，表示有T组样例
每组测试样例包含一个整数n(0 <= n <= 100)，代表每一个字有n%的几率无法输出

输出描述

输出T行，第i行为第i组测试用例的答案

示例1

输入: 

2
0 
100

输出: 

1
0

说明:

当故障率为0的时候一定能AC
当故障率为100%的时候一定不能AC

示例2

输入: 

2
1
2

输出: 

138057195
871666970

原站题解

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

C++ 解法, 执行用时: 175ms, 内存消耗: 1728K, 提交时间: 2021-06-09 13:52:16 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		long long _;
		cin>>_;
		cout<<(100-_)*(100-_)*796898467%998244353<<endl;
	}
}

pypy3 解法, 执行用时: 444ms, 内存消耗: 33244K, 提交时间: 2021-06-02 00:18:02 

gt=lambda:int(input())
M = 998244353
inv = pow(10000,M-2,M)
for _ in range(gt()):
    p = gt()
    print((100-p)**2*inv%M)

Python3 解法, 执行用时: 1135ms, 内存消耗: 5508K, 提交时间: 2022-10-27 21:09:53 

n=int(input())
for _ in range(n):
    nn=int(input())
    print((100-nn)**2*(pow(10000,998244351,998244353))%998244353)

上一题

© 2025 nowcoder.com