QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#816587#3082. Ascending MatrixyanshanjiahongWA 10ms9332kbC++143.0kb2024-12-16 15:14:262024-12-16 15:14:33

Judging History

你现在查看的是最新测评结果

  • [2024-12-16 15:14:33]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:9332kb
  • [2024-12-16 15:14:26]
  • 提交

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;
}

詳細信息

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'