链接：https://www.nowcoder.com/acm/contest/73/B
来源：牛客网
B.白兔的式子
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
已知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
输入
2
2 3 3 3
3 1 4 1
输出
9
27
备注:
T<=100000
1<=m<=n<=100000
0<=a,b<=109
这个题打个表能发现和杨辉三角有关系，小小了解一下
这个题就是所求位置对应的杨辉三角的系数，然后乘a的幂和b的幂。
因为数很大，不能直接用杨辉三角写，因为杨辉三角的系数也是组合数的阶乘相除，就要用到逆元。
求出来系数之后再用快速幂算一下a的幂和b的幂，就可以了。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int mod=;
ll f[maxn];
ll t,a,b,n,m;
void ff()
{
f[]=;
for(int i=;i<=;i++)
f[i]=(i*f[i-])%mod;
}
ll poww(ll n,ll m)//快速幂
{
ll ans = ;
while(m > )
{
if(m & )ans = (ans * n) % mod;
m = m >> ;
n = (n * n) % mod;
}
return ans;
}
ll cc(ll n,ll m)//组合数 阶乘逆元
{
ll ans=f[n];
ans=(ans*poww(f[m],mod-))%mod;
ans=(ans*poww(f[n-m],mod-))%mod;
return ans;
}
int main(){
ff();
int t;
int a,b,n,m;
cin>>t;
while(t--){
cin>>a>>b>>n>>m;
ll xishu=cc(n-,m-);
ll xa=poww(a,n-m);
ll xb=poww(b,m-);
ll ans=((xishu*xa)%mod*xb)%mod;
cout<<ans<<endl;
}
}