博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
杨辉三角+逆元 zoj 4006 牛客网 小白的式子
阅读量:5461 次
发布时间:2019-06-15

本文共 2382 字,大约阅读时间需要 7 分钟。

链接:

来源:牛客网

已知
f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i)。
对于其他情况f[i][j]=0

有T组询问,每次给出a,b,n,m,求f[n][m] mod (998244353)

输入描述:

第一行为一个整数T,表示询问个数。 接下来一共T行,每行四个整数a,b,n,m。

输出描述:

一共T行,每行一个整数,表示f[n][m] mod (998244353)

示例1

输入

22 3 3 33 1 4 1

输出

927
//注意由上一层的该项和前一项递推得到,那定与杨辉三角相联系//注意对答案取模时,乘一次,取一次,//ll ans=C(n-1,m-1)*pow_(a,n-m)%P*pow_(b,m-1)%P;#include
using namespace std;const int N=100010;const long long P=998244353;typedef long long ll;ll i,fac[N],inv[N];ll C(ll n,ll m){
return fac[n]*inv[m]%P*inv[n-m]%P;}ll pow_(ll a,ll b){ ll ans=1,tmp=a%P; while(b){ if(b&1) ans=ans*tmp%P; tmp=tmp*tmp%P; b/=2; } return ans;}int main(){ for(fac[0]=fac[1]=1,i=2;i
=0;i--)inv[i]=inv[i+1]*(i+1LL)%P; int t;ll a,b,n,m;scanf("%d",&t); while(t--){ scanf("%lld%lld%lld%lld",&a,&b,&n,&m); ll ans=C(n-1,m-1)*pow_(a,n-m)%P*pow_(b,m-1)%P; printf("%lld\n",ans); } return 0;}
View Code
Travel along the Line

Time Limit: 1 Second      
Memory Limit: 65536 KB

BaoBao is traveling along a line with infinite length.

At the beginning of his trip, he is standing at position 0. At the beginning of each second, if he is standing at position , with  probability he will move to position , with  probability he will move to position , and with  probability he will stay at position . Positions can be positive, 0, or negative.

DreamGrid, BaoBao's best friend, is waiting for him at position . BaoBao would like to meet DreamGrid at position  after exactly  seconds. Please help BaoBao calculate the probability he can get to position  after exactly  seconds.

It's easy to show that the answer can be represented as , where  and  are coprime integers, and  is not divisible by . Please print the value of  modulo , where  is the multiplicative inverse of  modulo .

Input

There are multiple test cases. The first line of the input contains an integer  (about 10), indicating the number of test cases. For each test case:

The first and only line contains two integers  and  (). Their meanings are described above.

Output

For each test case output one integer, indicating the answer.

Sample Input

32 -20 00 1

Sample Output

56250000410

Author: YE, Zicheng

Source: ZOJ Monthly, March 2018

该题即为杨辉三角的变形,因右边的一项是和左边的一项相等,即可转换成为杨辉三角的形式;

 

转载于:https://www.cnblogs.com/vainglory/p/8549756.html

你可能感兴趣的文章
【★】IT界8大恐怖预言
查看>>
DocumentManager
查看>>
Android 端闪存 应用——alpha 2.0 版
查看>>
MySQL C API 访问 MySQL 示例
查看>>
[kuangbin] M - Find a way(简单广搜)
查看>>
MysqL的root用户不允许远程连接
查看>>
hdu2955 Robberies(背包)
查看>>
MySQL数据库事务隔离级别(Transaction Isolation Level)
查看>>
Android之常用功能代码
查看>>
解决hash冲突的三个方法
查看>>
昔往今来,继续努力
查看>>
Visual C++ 2008入门经典中文版pdf
查看>>
#pragma data_seg
查看>>
Fetch-新一代Ajax API
查看>>
计算机网络-应用层/运输层
查看>>
shell用到的命令
查看>>
[BOI2011]MET-Meteors
查看>>
[洛谷P1892][codevs2597]团伙
查看>>
Eclipse中添加cmd命令行
查看>>
51Nod:1268 和为K的组合
查看>>