链接:
来源:牛客网有T组询问,每次给出a,b,n,m,求f[n][m] mod (998244353)
输入描述:
第一行为一个整数T,表示询问个数。 接下来一共T行,每行四个整数a,b,n,m。
输出描述:
一共T行,每行一个整数,表示f[n][m] mod (998244353)
输入
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;#includeusing 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;}
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该题即为杨辉三角的变形,因右边的一项是和左边的一项相等,即可转换成为杨辉三角的形式;