题目

题目描述

C 酱有一个$m\times n$的数表，行与列的编号都从$1$开始。令$f_{i,j}$表示表格第$i$行第$j$列内的数，那么对于表格的第$i(i>1)$行有

$$\{\begin{array}{l}{f}_{i,1}=a\times f_{i-1,1}\\ f_{i,j}=a\times f_{i-1,j}+b\times f_{i-1,j-1}\end{array}$$

然而 C 酱已经把表格中的数忘得差不多了，他现在只记得第$p$行的数。他希望你能够帮忙还原出部分位置的数值。

输入格式

输入第一行为$6$个整数$m,n,a,b,p,q$，其中$q$表示询问的个数。

接下来一行共$n$个整数，依次表示$f_{p,1},f_{p,2},\cdots ,f_{p,n}$。

接下来$q$行，每行两个整数$x,y$，表示 C 酱询问你$f_{x,y}￥的数值。

输出格式

输出共$q$行，依次表示每个询问的答案在模$998244353$意义下的取值。

即设答案可以表示为分式$\frac{a}{b}$ ，则输出整数$x$使得$b\times x\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}998244353)$且$0⩽x<998244353$。可以证明这样的整数$x$是唯一的。

样例

样例输入 1

5 4 1 1 3 5
1 0 0 0
5 2
3 1
1 2
2 3
4 3

样例输出 1

2
1
998244351
1
0

样例输入 2

10 5 233 2333 6 4
9 3 1 0 10
1 5
10 2
5 3
8 1

样例输出 2

110343631
118211750
770559638
488601

数据范围与提示

对于$100\%$的数据，保证$1⩽q⩽100,1⩽x,p⩽m,1⩽y⩽n,1⩽a,b<998244353,0⩽f_{i,j}<998244353$。

题解

40分算法

暴力把所有格子算出来
代码：

#include<iostream>
using namespace std;
int m,n,a,b,p,q;
long long ny,f[100010][110],MOD=998244353;
long long POW(long long a,long long b)
{
	long long ans=1;
	for(;b;b>>=1){
		if(b&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
	}
	return ans;
}
int main()
{
	cin>>m>>n>>a>>b>>p>>q;
	ny=POW(a,MOD-2);
	for(int i=1;i<=n;i++) cin>>f[p][i];
	for(int i=p+1;i<=m;i++) for(int j=1;j<=n;j++) f[i][j]=((a*f[i-1][j])%MOD+(b*f[i-1][j-1])%MOD)%MOD;
	for(int i=p-1;i>0;i--) for(int j=1;j<=n;j++) f[i][j]=(((f[i+1][j]-(b*f[i][j-1])%MOD)%MOD*ny)%MOD+MOD)%MOD;
	for(int i=1,x,y;i<=q;i++) cin>>x>>y,cout<<f[x][y]<<endl;
	return 0;
}

AC算法

我们先分类讨论，在第$p$行下和在第$p$行上
若在第$p$行下，我们可以由上面的两个点得出下面一个点

由题目可知，$f_{i,j}=a\times f_{i-1,j}+b\times f_{i-1,j-1}$

所以，我们考虑第$p$行中，要求的点$(x,y)$左侧的点$(p,i)$（即$i⩽y$），它对$(x,y)$的贡献就是$(p,i)$到$(x,y)$的路径条数（只能向右下或向下走）$\times a^{\cdots }\times b^{\cdots }$

我们只需要求$(p,i)$到$(x,y)$的路径条数和$a$、$b$的次数

假设$n=x-p,m=y-i$，那么，我们可以知道我们一共需要走$n$步，向右下走$m$步，所以路径数就是$C_n^m$

所以最终的结果就是：$C_n^m\times a^{n-m}\times b^m$

所以我们还能得到一个范围：$n⩾m$
终于，我们解决了$(x,y)$在在$p$行下，即$x>p$的情况，接下来，我们讨论一下$x<p$的情况

同样，我们可以通过下面的和他左边的点得到这个位置的值，$f_{i,j}=\frac{f_{i+1,j}}{a}-\frac{b\times f_{i,j-1}}{a}$，那么，问题就变成考虑第$p$行中，要求的点$(x,y)$左侧的点$(p,i)$（即$i⩽y$），它对$(x,y)$的贡献就是$(p,i)$到$(x,y)$的路径条数（只能向上或右走）$\times a^{\cdots }\times {\left(-\frac{b}{a}\right)}^{\cdots }$

同样假设$n=p-x,m=y-i$，但是，不一样的地方在于第一步必须向上走！所以，我们可以知道去掉先向上走的一步后，一共需要走$n+m-1$步，向右走$m$步，所以路径数就是$C_{n+m-1}^m$

所以最终的结果就是：$C_{n+m-1}^m\times a^n\times {\left(-\frac{b}{a}\right)}^m$

注意事项

1. 取模
2. 阶乘的逆元可以反着算，$invj{c}_i=invj{c}_{i+1}\ast (i+1)$，这样就避免了多次的$pow$
3. 提前保存$a$的逆元
4. 提前保存$-\frac{b}{a}$的次方，避免计算$-1^{y-i}$
5. $x<p$的情况中，是$C_{n+m-1}^m$

代码

#include<iostream>
using namespace std;
int n,m,p,q;
long long a,b,MOD=998244353,f[10100010],jc[10100010],cj[10100010],pa[10100010],pb[10100010],ap[10100010],bp[10100010];
/*
f：第p行的值
jc：阶乘
cj：阶乘的逆元
pa：a的次方
pb：b的次方
ap：pa的逆元
bp：-b/a的次方 
*/ 
long long POW(long long a,long long b)//快速幂 
{
	long long ans=1;
	for(;b;b>>=1){
		if(b&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
	}
	return ans;
}
long long C(int x,int y)//求组合数 
{
    if(x<0||y<0||y>x) return 0;
    return jc[x]*cj[y]%MOD*cj[x-y]%MOD;
}
int main()
{
    cin>>m>>n>>a>>b>>p>>q;
    jc[0]=pa[0]=pb[0]=ap[0]=bp[0]=1;
    for(int i=1;i<=10100000;i++) jc[i]=jc[i-1]*i%MOD;//暴力求阶乘 
    cj[10100000]=POW(jc[10100000],MOD-2);
    for(int i=10099999;i>=0;i--) cj[i]=cj[i+1]*(i+1)%MOD;//反向求阶乘的逆元 
    long long na=POW(a,MOD-2),nb=MOD-(b*na%MOD);
    for(int i=1;i<=10100000;i++) pa[i]=pa[i-1]*a%MOD,pb[i]=pb[i-1]*b%MOD,ap[i]=ap[i-1]*na%MOD,bp[i]=bp[i-1]*nb%MOD; 
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1,x,y;i<=q;i++){
        cin>>x>>y;
        if(x==p){cout<<f[y]<<endl;continue;}
        long long ans=0;
        if(x>p){for(int j=1;j<=y;j++) if(y-j<=x-p) ans=(ans+f[j]*C(x-p,y-j)%MOD*pa[x-y-p+j]%MOD*pb[y-j]%MOD)%MOD;}
		//括号很重要！不能删除 
		else for(int j=1;j<=y;j++) ans=(ans+f[j]*C(y-x+p-j-1,y-j)%MOD*ap[p-x]%MOD*bp[y-j]%MOD)%MOD;
		//分类讨论 
        cout<<ans<<endl;
    }
}

最后

以上就是碧蓝烤鸡为你收集整理的DTOJ Begin4028&DTOJ3603 table题目题解注意事项代码的全部内容，希望文章能够帮你解决DTOJ Begin4028&DTOJ3603 table题目题解注意事项代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。