QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#816587 | #3082. Ascending Matrix | yanshanjiahong | WA | 10ms | 9332kb | C++14 | 3.0kb | 2024-12-16 15:14:26 | 2024-12-16 15:14:33 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define lowbit(i) (i&-i)
#define int long long
using namespace std;
typedef long long ll;
const int N=405,M=55,mo=998244353;
const double PI=acos(-1);
void read(int &a){
int x=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')w=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
a=x*w;
}
int quick_power(int base,int x){
int res=1;
while(x){
if(x&1)res*=base,res%=mo;
base*=base,base%=mo;
x>>=1;
}
return res;
}
int n,m,k,r,c,v;
int g[N][N],f[N][N],p[N][N];
pii a[N][N];
void swp(int x,int y){
rep(i,1,k-1)
swap(p[x][i],p[y][i]);
}
int calc(){
int det=1;
rep(i,1,k-1){
if(!p[i][i]){
rep(j,i+1,k-1){
if(!p[j][i])continue;
swp(i,j),det=mo-det;
break;
}
if(!p[i][i])return 0;
}
int inv=quick_power(p[i][i],mo-2);
rep(j,i+1,k-1){
int mul=p[j][i]*inv%mo;
rep(l,i,k-1)
p[j][l]+=mo-p[i][l]*mul%mo,p[j][l]%=mo;
}
det*=p[i][i],det%=mo;
}
return det;
}
int C[N][N];
void countf(int s){
repp(i,s+1,0){
rep(j,0,m+k-1)
f[i][j]=0;
}
repp(i,s,0){
rep(j,0,m+k-2){
if(i>=r&&j>=c)continue;
else if(i==s&&j==0)f[i][j]=1;
else f[i][j]=(f[i+1][j]+(j?f[i][j-1]:0))%mo;
}
}
}
int y[N];
int lagrange(int x){
rep(i,1,k-1){
rep(j,1,k-1)
p[i][j]=(a[i][j].fir*x+a[i][j].sec)%mo;//printf("!%lld %lld:%lld\n",i,j,p[i][j]);
}
return calc();
}
int cg[N],ch[N];
signed main(){
read(n),read(m),read(k),read(r),read(c),read(v);
r=r+max(v-2,0ll),c=c+max(v-2,0ll);
//printf("?%lld %lld\n",r,c);
C[0][0]=1;
rep(i,1,400){
C[i][0]=1;
rep(j,1,i)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}
rep(i,n,n+k-2){
countf(i);
rep(j,m,m+k-2)
g[0][j]=(C[i+j][j]-f[0][j]+mo)%mo,a[i-n+1][j-m+1]=mp(f[0][j],g[0][j]);//printf("%lld %lld,%lld %lld\n",i-n+1,j-m+1,f[0][j],g[0][j]);
}
rep(i,1,k)
y[i]=lagrange(i);//printf("?%lld:%lld\n",i,y[i]);
cg[0]=1;
rep(i,1,k){
repp(j,k,0){
cg[j]=mo-i*cg[j]%mo;
if(j)cg[j]+=cg[j-1],cg[j]%=mo;
}
}
int ans=0;
rep(i,1,k){
int na=y[i];
rep(j,1,k)
if(i!=j)na*=quick_power(mo+i-j,mo-2),na%=mo;
ch[0]=cg[0]*quick_power(mo-i,mo-2)%mo;
rep(j,1,k)
ch[j]=(ch[j-1]-cg[j]+mo)*quick_power(i,mo-2)%mo;
ans+=ch[v-1]*na,ans%=mo;
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 10ms
memory: 9332kb
input:
148 129 48 144 105 13
output:
558145946
result:
wrong answer 1st lines differ - expected: '467058311', found: '558145946'