B3728 题解

· · 题解

B3728 题解

前置知识

题目解法

这题状态很好设计，又因为数据范围小，所以是一个明显的动态规划题目。

设 dp_{i,j} 为前 i 个骰子朝上一面的点数之和为 j 的方案数量，则答案为 \frac{dp_{n,m}}{6^n}。

转移方程和背包有点像，因为当前状态是由第 i-1 个骰子的状态与第 i 个骰子的六种选择方式来的，所以 dp_{i,j}=\displaystyle\sum_{k=1}^{6}dp_{i-1,j-k}。注意转移过程不要放到多组数据里面，要提前预处理好。

动态规划还有边界的处理，容易发现当 i=1,1\le j \le 6 时，有 1 种方案，其它情况没有方案。

答案不能直接算，要先预处理 6 的次幂的逆元，记得取模。另外，本题略微卡常，这里我使用了快读。

AC 代码

#include<iostream>
#define int long long //不开 ll 见祖宗
using namespace std;
const int mod=998244353; 
int read(){
    char c=getchar();
    int ans=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
    return ans;
}
int qpow(int a,int b){//快速幂，处理逆元用的
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int T,n,m,fsix[6000005],ans,dp[1005][6005];
signed main(){
    T=read();
    fsix[0]=1;
    int qwq=qpow(6,mod-2);//先算出 6 的逆元
    for(int i=1;i<=6e6;++i)fsix[i]=fsix[i-1]*qwq%mod;//预处理 6 的次幂的逆元
    for(int i=1;i<=6;++i)dp[1][i]=1;//dp 边界
    for(int i=2;i<=1000;++i){
        for(int j=1;j<=6000;++j){
            for(int k=1;k<=6;++k){
                dp[i][j]+=dp[i-1][j-k];//dp 转移
            }
            dp[i][j]%=mod;//记得取模
        }
    }
    while(T--){
        n=read();m=read();
        ans^=(dp[n][m]*fsix[n]%mod);//统计答案
    } 
    cout<<ans;
    return 0;
}