【记忆化搜索】掷骰子 hpuoj
阅读原文时间:2023年07月11日阅读:1

B. 掷骰子

单点时限: 2.0 sec

内存限制: 512 MB

骰子,中国传统民间娱乐用来投掷的博具,早在战国时期就已经被发明。

现在给你 n 个骰子,求 n 个骰子掷出点数之和为 a 的概率是多少。

输入格式

第一行输入一个整数 T,表示有 T 组测试数据(1≤T≤10) 
每组测试数据输入两个整数n,a,表示共有n个骰子,骰子点数总和为a(1≤n≤1000,n≤a≤6∗n)

输出格式

如题。答案对 109+7 取余。

样例

input

2
1 2
2 2

output

166666668
27777778

ps:由于自己的dp学的实在不好,所以使用记忆递归来写,个人觉得比dp更容易理解(大概是因为我是蒟蒻)。

#include
using namespace std;
typedef long long ll;
const int maxn = 1e6+;
const ll mod = 1e9+;
ll dp[][]; //dp[i][j]: 前i个股子可以组成j的方案数
bool vis[][]; //记忆数组
int T,n,a;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ //用扩展欧几里得来求逆元
if(!b){
d = a;
x = ;
y = ;
}else{
exgcd(b,a%b,d,x,y);
ll tmpx= x;
x = y;
y = tmpx -(a/b)*y;
}
}
ll inv(ll a,ll mod){ //返回逆元
ll d,x,y;
exgcd(a,mod,d,x,y);
return (x+mod)%mod;
}

ll DFS(int n,int le){ //当前第几个股子,当前剩余的数left
if(le <) return ; //剩余数为负数了
if(n == ){
if(le == ) return ; //股子用完了,剩余数为0就+1方案数
else return ;
}
if(vis[n][le]) return dp[n][le]; //记忆返回
int s = ;
for(int i = ;i<=&&i<=le;i++){ //选数
s += DFS(n-,le-i);
s %=mod;
}
vis[n][le] = ;
return dp[n][le] = s;//记忆化
}

ll solve(){
ll t = dp[n][a];
for(int i = ;i<=n;i++){
t = t*inv(,mod)%mod;
}
return t;
}

int main()
{
cin>>T;
while(T--){
cin>>n>>a;
DFS(n,a);
ll res = solve();
cout<<res<<endl;
}
return ;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章