自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:14:36，当前版本为作者最后更新于2023-04-17 21:30:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

$50$ 分做法

一道较为简单的概率题。

第一眼看到这个问题，应该很容易想到用到古典概型公式：

$P(A)=\frac{x}{y}$

其中 $x$ 表示 $A$ 事件包含的基本事件的个数，$y$ 代表基本事件的总数,基本事件为包含所有结果的等概率的事件。

这道题中 $y$ 的值非常简单，由于 $n$ 个骰子中每个骰子有6个面，根据乘法原理（或分步原理）及基本事件的定义容易得到本题的基本事件总数 $y=6^{n}$。

于是问题变为如何求 $x$。

这时再来看 $A$ 事件在本题的定义：

恰好有 $m$ 个骰子的朝上面为一号面（仅有一个点的面）的方案数？

“恰好”启发着我们用加法（或分类）原理来计算方案数，因为这样做我们大概率不需要容斥。

于是就可以想到这题的正解了！！

如果已经有 $m$ 个骰子是一号面朝上了，则剩下的 $(n-m)$ 个骰子就只能选择 $2$ 到 $6$ 共 $5$ 种选择。如果这 $m$ 个骰子已经选定了，则该情况的方案数 $5^{n-m}$。 而选定这 $m$ 个骰子的方案数就是从 $n$ 个骰子中选择 $m$ 个骰子的朝上面为一号面的方案数，即 $C_{n}^{m}$。根据分步原理，就能得到：

$x=C_{n}^{m}5^{n-m}$

把组合数拆开后，就得到 $P(A)$ 的表达式了！（别忘了，我们还要将每次的结果模去 $998244353$）

$P(A)=\frac{5^{n-m}n!}{6^{n}m!(n-m)!}$

由于还要模 $998244353$ ,且询问次数 $T$、$n$ 与 $m$ 的范围都达到了 $5e6$,则需要线性预处理 $i!$，$(i!)^{-1}$，$6^{i}$,$(5^{i})^{-1}$。（但这些不是这道题的重点，不加详解，还不会的可以前往洛谷P3811【模板】乘法逆元 学习相关知识。）最后每次只用 $O(T)$ 求出每次询问的答案并按位异或累计即可。总复杂度 $O(n+T)$，足以通过此题。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ci const int
ci mod=998244353;
ci N=5e6+5;
ll inv[N],mul[N],ans,mul5[N],inv6[N];
int t;
ll qp(ll a,ll b){
	if(b==0)rt 1;
	ll c=qp(a,b/2);
	c=c*c%mod;
	if(b&1)c=c*a%mod;
	return c;
}
void preset(){//预处理
	mul[0]=mul5[0]=1;
	for(int i=1;i<=N-5;i++){
		mul[i]=mul[i-1]*i%mod;
		mul5[i]=mul5[i-1]*5%mod;
	}
	inv[N-5]=qp(mul[N-5],mod-2);
	inv6[N-5]=qp(qp(6,N-5),mod-2);
	for(int i=N-6;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
		inv6[i]=inv6[i+1]*6%mod;
	}
}
int main(){
	cin >>t;
	preset();
	for(int i=1,n,m;i<=t;i++){
		scanf("%d%d",&n,&m);
		ans^=mul5[n-m]*mul[n]%mod*inv6[n]%mod*inv[m]%mod*inv[n-m]%mod;
	}
	cout <<ans;
	return 0;
}

什么，你做完了？！提交了代码然后……WA了？！

你这时回去看输入输出格式，发现：

共输出两行。

第一行输出一个仅含小写字母的字符串，表示『骰』这个字的汉语拼音（不含声调）。 啊啊啊这是什么鬼？NOI 大纲里好像没有这方面的知识啊？

这个对于只会敲代码的 OIer 们来讲超纲了，因为 NOI 大纲里根本没有认识某些汉字的拼音这项知识。

由于接下来的内容有些超纲，只想练习敲代码的 OIer 们可以选择拿到 $50$ 分的部分分就继续敲别的题了。

满分做法

在 $50$ 分的基础上，我们现在需要知道汉字“骰”的拼音。

这里介绍两个新的概念：

$1$.拼音，是拼读音节的过程，就是按照普通话音节的构成规律，把声母、介母、韵母急速连续拼合并加上声调而成为一个音节。

$2$.字典是为字词提供音韵、意思解释、例句、用法等等的工具书。

在知道这些定义的前提下，要知道“骰”的拼音，我们有以下几种途径：

$1$.通过日常所积累的知识，直接说出其拼音。（这需要较强的语文功底，比较困难。）

$2$.通过查字典，找到骰字的拼音。

对于第二条途径，我们一般采用字形法或五笔输入法 。 请读者根据指引自行操作并得到答案，并用喜欢的输出方式输出其读音，记得换行。