NC233874. Turtles
描述
输入描述
第一行包含了,
。
后面行，每行有
个字符，第
行第
个字符表示
的状态（'.'是空格，'#'是障碍）。
输出描述
一行，对取模后的从起点到终点的不同路径对数。
示例1
输入:
4 5 ..... .###. .###. .....
输出:
1
示例2
输入:
2 3 ... ...
输出:
1
C++(g++ 7.5.0) 解法, 执行用时: 288ms, 内存消耗: 44656K, 提交时间: 2022-08-23 20:52:13
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 105, mod = 1e9 + 7 ;
int qsm(int a,int b)
{
int ans=1 ;
while(b)
{
if(b&1) ans=(ll)ans*a%mod ;
a=(ll)a*a%mod ; b>>=1 ;
}
return ans ;
}
struct Matrix
{
int m[MAXN][MAXN] ;
Matrix() { memset(m,0,sizeof(m)) ; }
} ;
namespace Mat
{
int A[MAXN][MAXN],B[MAXN][MAXN<<1] ;
Matrix mat_ret,mat_lin ;
#define up(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,a,b) for(int i=(a);i>=(b);--i)
#define VI vector<int>
void ad(int &x,int y) { x+=y ; if(x>=mod) x-=mod ; }
void dl(int &x,int y) { x-=y ; if(x<0) x+=mod ; }
int det(const Matrix &a,int n)//矩阵求行列式
{
up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
int ret=1 ;
up(i,1,n)
{
int u=i ; up(j,i+1,n) if(A[j][i]) { u=j ; break ; }
if(u!=i) { up(j,i,n) swap(A[u][j],A[i][j]) ; ret=(ll)ret*(mod-1)%mod ; }
if(!A[i][i]) return 0 ; int Iv=qsm(A[i][i],mod-2) ;
up(j,i+1,n)
{
int tmp=(ll)A[j][i]*Iv%mod ;
up(k,i,n) dl(A[j][k],(ll)tmp*A[i][k]%mod) ;
}
ret=(ll)ret*A[i][i]%mod ;
}
return ret ;
}
Matrix mat_inv(const Matrix &a,int n)//矩阵求逆
{
memset(B,0,sizeof(B)) ; int l=n<<1 ;
up(i,1,n)up(j,1,n) B[i][j]=a.m[i][j] ;
up(i,1,n) B[i][i+n]=1 ;
up(i,1,n)
{
int u=i ; up(j,i+1,n) if(B[j][i]) { u=j ; break ; }
up(j,1,l) swap(B[i][j],B[u][j]) ;
int Iv=qsm(B[i][i],mod-2) ;
up(j,1,l)
{
if(i==j) continue ;
int tmp=(ll)B[j][i]*Iv%mod ;
up(k,i,n) dl(B[j][k],(ll)tmp*B[i][k]%mod) ;
up(k,n+1,l) dl(B[j][k],(ll)tmp*B[i][k]%mod) ;
}
up(j,i,n) B[i][j]=(ll)B[i][j]*Iv%mod ;
up(j,n+1,l) B[i][j]=(ll)B[i][j]*Iv%mod ;
}
memset(mat_ret.m,0,sizeof(mat_ret.m)) ;
up(i,1,n)up(j,1,n) mat_ret.m[i][j]=B[i][j+n] ;
return mat_ret ;
}
int calc_r(const Matrix &a,int n)//矩阵求秩
{
up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
int ret=0 ;
up(i,1,n)
{
if(!A[i][i])
{
int u=-1 ;
up(j,i+1,n) if(A[j][i]) { u=j ; break ; }
if(u==-1) continue ;
up(j,i,n) swap(A[i][j],A[u][j]) ;
}
ret++ ; int Iv=qsm(A[i][i],mod-2) ;
up(j,i+1,n)
{
int tmp=(ll)A[j][i]*Iv%mod ;
up(k,i,n) dl(A[j][k],(ll)tmp*A[i][k]%mod) ;
}
}
return ret ;
}
Matrix get_adjoint_matrix_full(const Matrix &a,int n)//求满秩矩阵伴随矩阵
{
Matrix Iv=mat_inv(a,n) ; int Z=det(a,n) ;
up(i,1,n)up(j,1,n) mat_ret.m[j][i]=(ll)Iv.m[i][j]*Z%mod ;
return mat_ret ;
}
int us[MAXN][MAXN],Inv[MAXN] ;
VI insert(VI Z,int n,int id)
{
VI bel(n+1,0) ; bel[id]=1 ; bel[0]=-1 ;
rep(i,n,1) if(Z[i])
{
if(!A[i][i])
{
rep(j,i,1) A[i][j]=Z[j] ;
Inv[i]=qsm(A[i][i],mod-2) ;
up(j,1,n) us[i][j]=bel[j] ;
return bel ;
}
int tmp=(ll)Inv[i]*Z[i]%mod ;
rep(j,i,1) dl(Z[j],(ll)tmp*A[i][j]%mod) ;
up(j,1,n) dl(bel[j],(ll)tmp*us[i][j]%mod) ;
}
bel[0]=0 ; return bel ;
}
VI get_G(const Matrix &a,int n,int op) //求线性相关系数
{
VI ret ;
up(i,1,n)up(j,1,n) A[i][j]=a.m[i][j] ;
if(op) up(i,1,n)up(j,1,n) B[j][i]=A[i][j] ;
else up(i,1,n)up(j,1,n) B[i][j]=A[i][j] ;
memset(A,0,sizeof(A)) ; memset(us,0,sizeof(us)) ;
up(i,1,n)
{
VI Z(n+1,0) ;
up(j,1,n) Z[j]=B[j][i] ;
ret=insert(Z,n,i) ;
if(ret[0]!=-1) return ret ;
}return ret ;
}
Matrix get_adjoint_matrix_one(const Matrix &a,int n)//求秩为n-1的矩阵伴随矩阵
{
VI Q = get_G(a,n,0) ; // 列向量组系数
VI P = get_G(a,n,1) ; // 行向量组系数
int c=-1,r=-1 ;
up(i,1,n) if(Q[i]) { c=i ; break ; }
up(i,1,n) if(P[i]) { r=i ; break ; }
up(i,1,n) if(i!=r) up(j,1,n) if(j!=c)
mat_lin.m[i-(i>r)][j-(j>c)]=a.m[i][j] ;
int Ivq=qsm(Q[c],mod-2),Ivp=qsm(P[r],mod-2) ;
int Iv=(ll)Ivp*Ivq%mod ;
mat_ret.m[r][c]=det(mat_lin,n-1) ;
if((r+c)&1) mat_ret.m[r][c]=mod-mat_ret.m[r][c] ;
up(i,1,n)up(j,1,n)
{
int val=(ll)P[i]*Q[j]%mod*Iv%mod*mat_ret.m[r][c]%mod ;
mat_ret.m[i][j]=val ;
}
return mat_ret ;
}
// A * A* = |A| * I
Matrix get_adjoint_matrix(const Matrix &a,int n)//求矩阵的伴随矩阵
{
int Z=calc_r(a,n) ;
if(Z==n) return get_adjoint_matrix_full(a,n) ;
else if(Z==n-1) return get_adjoint_matrix_one(a,n) ;
else
{
memset(mat_ret.m,0,sizeof(mat_ret.m)) ;
return mat_ret ;
}
}
}
const int N = 3005 ;
const int M = 105 ;
int n,m ;
int dp[N][N] ;
char s[N][N] ;
int calc(int sx,int sy,int tx,int ty)
{
memset(dp,0,sizeof(dp)) ;
if(s[sx][sy]=='#') return 0 ;
dp[sx][sy]=1 ;
for(int i=sx;i<=tx;++i)
for(int j=sy;j<=ty;j++)
if(s[i][j]!='#')
{
if(i>sx) (dp[i][j]+=dp[i-1][j])%=mod ;
if(j>sy) (dp[i][j]+=dp[i][j-1])%=mod ;
}
return dp[tx][ty] ;
}
void solve()
{
scanf("%d%d",&n,&m) ;
for(int i=1;i<=n;++i) scanf("%s",s[i]+1) ;
printf("%lld\n",((ll)calc(1,2,n-1,m)*calc(2,1,n,m-1)%mod-(ll)calc(1,2,n,m-1)*calc(2,1,n-1,m)%mod+mod)%mod) ;
}
int main()
{
/*jc[0]=1 ;
for(int i=1;i<N;++i) jc[i]=(ll)jc[i-1]*i%mod ;
inv[N-1]=qsm(jc[N-1],mod-2) ;
for(int i=N-1;i>=1;--i) inv[i-1]=(ll)inv[i]*i%mod ;*/
int T=1 ;// scanf("%d",&T) ;
while(T--) solve() ;
return 0 ;
}
C++ 解法, 执行用时: 438ms, 内存消耗: 79916K, 提交时间: 2022-04-05 15:21:36
#include<bits/stdc++.h>
#ifndef debug
#define debug(args...)
#define debugArr(begin,end)
#endif
#define all(v) v.begin(),v.end()
#define Case(T) int TTT;cin>>TTT;for(int T=1; T<=TTT; ++T)
#define close_ios() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using ll=long long;
const int N=3000+10,mod=1e9+7;
int n,m;
char g[N][N];
ll f[N][N];
ll solve(int a,int b,int c,int d){
function<int(int,int)> in_range=[=](int x,int y){
return x>=a&&x<=c&&y>=b&&y<=d;
};
for (int i=a; i<=c; ++i)
for(int j=b; j<=d; ++j){
if(g[i][j]=='#') f[i][j]=0;
else if(i==a&&j==b) f[i][j]=1;
else f[i][j]=(in_range(i-1,j)*f[i-1][j]+in_range(i,j-1)*f[i][j-1])%mod;
}
return f[c][d]*(a<=c&&b<=d);
}
int main() {
close_ios();
cin>>n>>m;
for (int i=1; i<=n; ++i) cin>>(g[i]+1);
cout<<(solve(1,2,n-1,m)*solve(2,1,n,m-1)%mod+mod-solve(1,2,n,m-1)*solve(2,1,n-1,m)%mod)%mod;
return 0;
}
/*
*/