QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130863#6669. MapaXY_Eleven0 0ms0kbC++234.0kb2023-07-25 14:52:392023-07-25 14:52:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-25 14:52:42]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-07-25 14:52:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define cDB const DB
#define cchar const char
#define inint inline int
#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 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 x0 x00
#define y1 y11
invoid input(int &N_,int A_[],bool F_)
{
    if(F_) inint(N_);
    For(i,1,N_) inint(A_[i]);
}
inLL md(LL w1,cLL w2)
{
    w1%=w2; if(w1<0ll) w1+=w2;
    return w1;
}
invoid add(LL &w1,cLL w2,cLL 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; }
template <typename Type>
inlint lower(Type W_,vector <Type> &V_)
{
    return lower_bound(V_.begin(),V_.end(),W_)-V_.begin();
}
//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); }
cint N=120,L=6100;
int n,q,siz;
cLL mod=1e9+97;
char s[N];
LL d[N][N],ans[N];
invoid work(int m)
{
    if(!m) return ;
    /*printf("m=%d\n",m);
    For(i,1,m)
    {
        For(j,1,m)
            printf("%d ",d[i][j]);
        printf("=%d\n",d[i][0]);
        puts("");
    }*/
    For_(i,1,m)
    {
        LL x=d[m][m]*inv(d[i][m],mod)%mod;
        For(j,0,m)
            d[i][j]=md(d[i][j]*x-d[m][j],mod);
    }
    work(m-1);
    LL t=d[m][0];
    For_(i,1,m)
        add(t,-ans[i]*d[m][i],mod);
    ans[m]=t*inv(d[m][m],mod)%mod;
}
invoid solve1()
{
    inint(n);
    For(i,1,n)
    {
        LL a,b;
        scanf("%lld%lld",&a,&b);
        LL s=1ll;
        For(j,1,n)
        {
            d[i][j]=s;
            mul(s,a,mod);
        }
        d[i][0]=b;
    }
    work(n);
    outint(n*30);
    For(i,1,n) Rof(j,0,29) putchar('0'+((ans[i]>>j)&1));
    puts("");
}
invoid solve2()
{
    in3(n,q,siz);
    scanf("%s",s+1);
    For(i,1,n) For(j,1,30)
        ans[i]=ans[i]<<1|(s[(i-1)*30+j]-'0');
    while(q--)
    {
        LL t,s=1ll,c=0ll;
        inll(t);
        For(i,1,n)
        {
            add(c,s*ans[i],mod);
            mul(s,t,mod);
        }
        outll(c);
    }
}
int main()
{
    //freopen("out.txt","w",stdout);
    int T;
    inint(T);
    if(T&1) solve1();
    else solve2();
    return 0;
}
/*
1
4
123 456
789 666
666 233
1331 14641

2
4 4
120
010111010101001011010001111011000000101101011010011011011001110000110101101110000101101010010011100101011010111100000100
1331
789
123
666
*/

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1
100
495528311 963488152
269613430 443544124
700489871 792354118
151890319 506569919
180452297 13229948
684464994 543841485
978085128 903812192
238355172 441140842
28061035 783291471
530823766 718942732
936853023 439421263
201361623 226633955
304644844 778868118
864860135 461524170
88300500 6959354...

output:

3000
0100001000011011010101011111000001110111010011001101110110000001101110010100000010011011110111000010100100010111110100111110000100011000101000010011000000001101011011100100010010001101101001001101011010111000001001111100001000100111011110011110100010101010100011010100010010110111100011111011000...

input:

2
100 79 3000
0100001000011011010101011111000001110111010011001101110110000001101110010100000010011011110111000010100100010111110100111110000100011000101000010011000000001101011011100100010010001101101001001101011010111000001001111100001000100111011110011110100010101010100011010100010010110111100011...

output:


result: