自动搬运

查看原文

来自洛谷，原作者为

	Milthm ?

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

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

以下是正文

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;
}