B3718

未来姚班zyl · 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 分的基础上，我们现在需要知道汉字“骰”的拼音。

这里介绍两个新的概念：