f[i][j]表示向上扩展了i行,向右扩展了j列的方案数
显然f[i][j]=f[i-1][j]*j+f[i][j-1]*i;但是这样会有重复的
怎么去重是关键,top行和right列对称操作会重复算,所以最后为
f[i][j]=f[i-1][j]*j+f[i][j-1]*i-(i-1)*(j-1)*f[i-1][j-1];
#include <bits/stdc++.h> #define inf 2333333333333333 #define N 3010 #define p(a) putchar(a) #define For(i,a,b) for(long long i=a;i<=b;++i) //by war //2020.7.21 using namespace std; long long a,b,c,d,mod=998244353; long long f[N][N]; void in(long long &x){ long long y=1;char c=getchar();x=0; while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();} x*=y; } void o(long long x){ if(x<0){p('-');x=-x;} if(x>9)o(x/10); p(x%10+'0'); } long long dfs(long long x,long long y){ if(x<a || y<b) return 0; if(~f[x][y]) return f[x][y]; long long ans=0; if(x==a) ans+=x*dfs(x,y-1),ans%=mod; if(y==b) ans+=y*dfs(x-1,y),ans%=mod; if(x>a && y>b) ans+=((x*dfs(x,y-1)%mod+y*dfs(x-1,y)%mod)%mod-(x-1)*(y-1)*dfs(x-1,y-1)%mod+mod)%mod,ans%=mod; f[x][y]=(ans+mod)%mod; return f[x][y]; } signed main(){ in(a);in(b);in(c);in(d); memset(f,-1,sizeof f); f[a][b]=1; o(dfs(c,d)); return 0; }