QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140278#4794. SalajXY_ElevenWA 154ms109920kbC++233.8kb2023-08-15 16:51:142023-08-15 16:51:16

Judging History

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

  • [2023-08-15 16:51:16]
  • 评测
  • 测评结果:WA
  • 用时:154ms
  • 内存:109920kb
  • [2023-08-15 16:51:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define pii pair<int,int>
#define pil pair<int,LL>
#define mii map<int,int>
#define miig map<int,int,greater<int> >
#define mil map<int,LL>
#define in128 __int128
#define cint const int
#define cLL const LL
#define cDB const DB
#define cchar const char
#define invoid inline void
#define inLL inline LL
#define inlint inline int
#define inbool inline bool
#define inl128 inline __int128
#define inDB inline double
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) ((LL)(e))
#define pb push_back
#define ft first
#define sc second
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define x0 x00
#define y1 y11
#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define fout fflush(stdout)
invoid input(int &N_,int A_[],bool F_)
{
    if(F_) inint(N_);
    For(i,1,N_) inint(A_[i]);
}
template <typename Type>
inline Type md(Type w1,const Type w2)
{
    w1%=w2; if(w1<0) w1+=w2;
    return w1;
}
template <typename Type>
invoid add(Type &w1,const Type w2,const Type M_)
{ w1=md(w1+w2,M_); }
invoid mul(LL &w1,cLL w2,cLL M_)
{ w1=md(w1*w2,M_); }
inLL gcd(LL X_,LL Y_)
{
    LL R_=X_%Y_;
    while(R_)
    { X_=Y_; Y_=R_; R_=X_%Y_; }
    return Y_;
}
invoid ex_gcd(LL &X_,LL &Y_,LL A_,LL B_)
{
    if(!B_)
    {
        X_=1ll; Y_=0ll;
        return ;
    }
    ex_gcd(Y_,X_,B_,A_%B_);
    X_=md(X_,B_); Y_=(1ll-X_*A_)/B_;
}
inLL inv(LL A_,LL B_)
{
    LL X_=0ll,Y_=0ll;
    ex_gcd(X_,Y_,A_,B_);
    return X_;
}
inLL pw(LL X_,LL Y_,LL M_)
{
    LL S_=1ll;
    while(Y_)
    {
        if(Y_&1) mul(S_,X_,M_);
        Y_>>=1;
        mul(X_,X_,M_);
    }
    return S_;
}
template <typename Type>
invoid get_min(Type &w1,const Type w2)
{ if(w2<w1) w1=w2; }
template <typename Type>
invoid get_max(Type &w1,const Type w2)
{ if(w2>w1) w1=w2; }
//inLL A(cint N_,cint M_)
//{ return (N_>=M_?md(d1[N_]*d2[N_-M_],mod):0ll); }
//inLL C(cint N_,cint M_)
//{ return (N_>=M_?md(d1[N_]*md(d2[M_]*d2[N_-M_],mod),mod):0ll); }
//mt19937 gen(time(NULL));
//mt19937_64 gen(time(NULL));
//cLL base[]={166686661,188868881},mod[]={1686688681,1666868881};
//cLL base[]={166686661,188868881},mod[]={1686688681,1666868881},inter=1861;
//cLL mod[]={1e9+7,1e9+9,1e9+21,1e9+33};
//cLL mod=998244353;
cint N=52,M=2510;
int n,m;
LL mod;
LL dp[M][N][N],sum[M][N][N];
invoid solve()
{
    inpr(n,m); inll(mod);
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));
    dp[0][1][1]=1ll;
    For(i,0,m) For(j,1,n) For(k,1,j)
    {
        if(k) add(sum[i][j][k],sum[i][j][k-1],mod);
        add(dp[i][j][k],sum[i][j][k],mod);
        exc(!dp[i][j][k]);
        add(sum[i+1][j][k+1],dp[i][j][k],mod);
        if(j<n)
            add(dp[i+1][j+1][k],dp[i][j][k],mod);
        else// if(i-(n-1)>k*(k-1)/2)
            add(dp[i+1][j][k],dp[i][j][k],mod);
    }
    For(i,1,m)
    {
        LL sum=0ll;
        For(j,1,n) For(k,1,j)
            add(sum,dp[i][j][k],mod);
        printf("%lld%c",sum," \n"[i==m]);
    }
}
int main()
{
    int _;
    inint(_);
    while(_--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 109708kb

input:

2
5 10 666013
6 9 10

output:

1 2 4 9 21 50 110 209 351 546
1 2 4 9 1 1 6 0 7

result:

ok 19 numbers

Test #2:

score: -100
Wrong Answer
time: 154ms
memory: 109920kb

input:

10
31 248 8654701
13 11 331266209
33 517 52876477
26 580 675225807
48 2029 311070528
26 31 327981899
39 25 644128037
29 776 464963196
43 799 451592950
25 184 564388620

output:

1 2 4 9 21 51 127 323 835 2188 5798 15511 41835 113634 310572 853467 2356779 6536382 889882 7578514 4072343 2646977 4649285 7797829 7894657 8630011 5369867 7539674 4332126 8201689 8589675 2709364 4018535 3531401 5490003 4890382 334630 1280966 7295275 4971992 1680824 7744560 2450701 2716471 1097918 5...

result:

wrong answer 1102nd numbers differ - expected: '546820274', found: '546820275'