Submission #50229845

---

Source Code Expand

// LUOGU_RID: 146743310
#include<bits/stdc++.h>
#define ll long long
#define mxn 200003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define ld long double
#define umap unordered_map
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
#define pq priority_queue
using namespace std;
inline ll gcd(ll x,ll y){
	while(y^=x^=y^=x%=y);
	return x;
}
int n,m,ans,a[18],d[1214830];
ll s,g,f[18];
queue<int>q;
ll calc(){
	ll ans=0;
	rep(i,1,n)ans+=f[i-1]*a[i];
	return ans;
}
int get(ll x){
	int ans=0;
	rep(i,1,n){
		ans+=x%(i*2);
		x/=i*2;
	}
	return ans;
}
signed main(){
	cin>>n>>m;
	f[0]=1;
	rep(i,1,n)f[i]=f[i-1]*2*i;
	rep(i,1,n)cin>>a[i];
	s=calc(),g=f[n]-1;
	rep(i,1,m){
		rep(j,1,n)cin>>a[j];
		g=gcd(g,calc());
	}
	if(g>1214827){
		ans=1e9;
		for(ll i=s%g==0?g:s%g;i<f[n];i+=g){
			ans=min(ans,get(i));
		}
		cout<<ans;
	}else{
		memset(d,-1,sizeof(d));
		rept(i,0,n){
			d[f[i]%g]=1;
			q.push(f[i]%g);
		}
		while(q.size()){
			int x=q.front();q.pop();
			rept(i,0,n){
				int y=(x+f[i])%g;
				if(d[y]==-1){
					d[y]=d[x]+1;
					q.push(y);
				}
			}
		}
		cout<<d[s%g];
	}
	return 0;
}

Submission Info

Judge Result