列表

详情

NC213962. RikkawithCompositeNumber

描述

Rikka is a professional problem setter. Today, she is going to generate test cases for a problem about Composite Number.
To randomly generate composite numbers, Rikka starts from a non-empty subset D of digits and integer c = 0, and then generates in turns. In each turn:
  1. Rikka selects a digit d from D uniformly at random, and then changes c to ;
  2. If c has already been a composite integer, Rikka takes c as the result. Otherwise, Rikka returns to Step 1 and starts a new turn.
The time cost of a generator is crucial. Therefore, Rikka wants you to calculate the expected number of the turns used by the generator to generate a composite number.
A positive integer n is a composite integer if and only if there exists an integer satisfying k is a factor of n.

输入描述

The first line contains a 01-string of length 9. The i-th character is 1 if and only if digit i is inside D.
The input guarantees that D is not empty.

输出描述

Output a single integer, representing the expected number of turns.
The answer is guaranteed to be a rational number. You are required to output the answer module 998244353. Formally, if the simplest fraction representation of the answer is , you need to output .

示例1

输入: 

100000000

输出: 

3

说明:

The generator must return 111 in the third turn.

示例2

输入: 

001100000

输出: 

499122178

说明:

There are 3 possibilities:
1. Return 4 in the first turn, with probability \frac{1}{2}.
2. Return 33 in the second turn, with probability \frac{1}{4}.
3. Return 34 in the second turn, with probability \frac{1}{4}.
Therefore, the expected number of turns is \frac{3}{2}.

原站题解

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

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-11-22 09:50:12 

#include <iostream>
#include <cstdio>
using namespace std;
char s[20];
int g,P=998244353,ans;
int qpow(int x,int y)
{
	int r=1;
	while(y)
	{
		if(y&1)r=1ll*r*x%P;
		x=1ll*x*x%P;
		y/=2;
	}
	return r;
}
int chk(long long x)
{
	for(int i=2;1ll*i*i<=x;i++)if(x%i==0)return 1;
	return 0;
}
void dfs(long long x,int y,int z)
{
	if(chk(x))ans=(ans+1ll*z*y)%P;
	else
	{
		for(int i=1;i<=9;i++)if(s[i]=='1')dfs(x*10+i,1ll*y*g%P,z+1);
	}
}
int main()
{
	scanf("%s",s+1);
	for(int i=1;i<=9;i++)if(s[i]=='1')g++;
	g=qpow(g,P-2);
	dfs(0,1,0);
	cout<<ans<<endl;
	return 0;
}

pypy3 解法, 执行用时: 90ms, 内存消耗: 24788K, 提交时间: 2022-11-17 22:15:53 

s = input()

mod = 998244353

cnt = s.count('1')
inv = pow(cnt, mod - 2, mod)

def is_prime(x):
    for i in range(2, x):
        if x % i == 0:
            return False
        if i * i > x:
            break
    return True

ans = 0

def dfs(x, prob, step):
    if not is_prime(x):
        global ans
        ans = (ans + prob * step) % mod
        return
    
    for i in range(9):
        if s[i] == '1':
            dfs(10 * x + i + 1, prob * inv % mod, step + 1)

dfs(0, 1, 0)

print(ans)

上一题

© 2024 nowcoder.com