Submission #49369027

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define fir first
#define sec second

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

ll gcd(ll A,ll B){
    if(!B) return A;
    return gcd(B,A%B);
}

int n,m;
ll A,B[51],base[51],M,G;

namespace Subtask1{
    bool vis[1214827+5];
    int f[1214827+5];
    queue<int> Q;
    int main(){
        for(int i=1;i<=n;++i){
            vis[base[i-1]%G]=true;
            f[base[i-1]%G]=1;
            Q.push(base[i-1]%G);
        }
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=1,v;i<=n;++i){
                v=(u+base[i-1]%G)%G;
                if(!vis[v]){
                    vis[v]=true;
                    f[v]=f[u]+1;
                    Q.push(v);
                }
            }
        }
        printf("%d\n",f[A%G]);
        return 0;
    }
}

int ans;
namespace Subtask2{
    inline int calc(ll X){
        int res=0;
        for(int i=n;i>=1;--i){
            res+=X/base[i-1];
            X%=base[i-1];
        }
        return res;
    }
    int main(){;
        for(int k=0;k<=M/G;++k){
            if((A+k*G)%M) ans=min(ans,calc((A+k*G)%M));
        }
        printf("%d\n",ans);
        return 0;
    }
}

int main(){
    // freopen("112F.in","r",stdin);
    n=read(),m=read();
    base[0]=1;
    for(int i=1;i<=n;++i) base[i]=base[i-1]*2*i;
    M=base[n]-1;
    for(int i=1,x;i<=n;++i) x=read(),A=(A+x*base[i-1])%M,ans+=x;
    G=M;
    for(int i=1;i<=m;++i){
        for(int j=1,x;j<=n;++j) x=read(),B[i]=(B[i]+x*base[j-1])%M;
        G=gcd(G,B[i]);
    }
    if(G<=M/G) return Subtask1::main();
    else return Subtask2::main();
    return 0;
}

Submission Info

Judge Result