列表

详情

NC224207. 擅长解密的小红同学

描述

小红来到了一个机关前，准备破解机关的密码门。
已知机关的密码是一串数字（'0'~'9'）。小红经过不懈的努力，终于破解了每个数字出现的次数。但她并不知道每个数字出现的先后次序。
于是她只能随机来尝试破解密码。不过这个机关有个特点：每当小红输入一次尝试之后，密码都会重置。不过每个数字出现的次数不变。
小红想知道自己尝试次数的期望是多少？

输入描述

一行共 10 个非负整数  ，分别代表 '0'~'9' 每个数字的出现次数。
 ，且保证所有  不会全为0。

输出描述

小红尝试次数的期望，对  取模。
可以证明，该期望一定为有理数。如果该期望为分数，请输出分数取模的值。
分数取模的定义：  ，等价于

示例1

输入: 

0 2 0 0 0 0 0 0 0 0

输出: 

1

说明:

已知数字 1 出现了 2 次，那么密码只有可能是 "11" ，小红只需要一次输入即可破解。

示例2

输入: 

1 1 0 0 0 0 0 0 0 0

输出: 

2

说明:

已知数字 0 出现了 1 次，数字 1 出现了 1 次，那么密码可能是 "01" 或者 "10" 。由于密码可能会重置，因此小红每次尝试的成功概率为 。

尝试次数的期望为

原站题解

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

C++ 解法, 执行用时: 69ms, 内存消耗: 39544K, 提交时间: 2021-08-07 22:44:59 

#include<bits/stdc++.h>
using namespace std;
#define Mod 1000000007
#define For(i,x,y)for(i=x;i<=(y);i++)
int fac[10000005],a[11];
int ksm(int x,int y)
{
	return(!y?1:1LL*ksm(1LL*x*x%Mod,y>>1)*(y&1?x:1)%Mod);
}
int main()
{
	int i;
	For(i,0,9)cin>>a[i],a[10]+=a[i];
	fac[0]=1;
	For(i,1,a[10])fac[i]=1LL*fac[i-1]*i%Mod;
	a[10]=fac[a[10]];
	For(i,0,9)a[10]=1LL*a[10]*ksm(fac[a[i]],Mod-2)%Mod;
	cout<<a[10];
	return 0;
}

pypy3 解法, 执行用时: 186ms, 内存消耗: 99516K, 提交时间: 2022-10-21 18:05:34 

cnt=[int(x) for x in input().split()]
mod=10**9+7
n=sum(cnt)
f=[1]*(n+1)

for i in range(1,n+1):
    f[i]=f[i-1]*i
    f[i]%=mod


    
res=f[sum(cnt)]


for i in range(10):
    res*=pow(f[cnt[i]],mod-2,mod)
    res%=mod

print(res)

上一题

© 2024 nowcoder.com