石子游戏

这个的部分分数 \(50pts\) 需要使用 \(SG\) 函数。。

因为上次颓废，然后就没有学。。。

一个堆的 \(SG\) 函数就是最高的那个 \(SG\)

然后我们的 \(SG\) 函数就是递推而成。

我们将这个东西所能到达的所有状态的 \(SG\) 值排序，之后我们就可以找到第一个没出现的非负整数，这个就是他的 \(SG\) 值。

然后这样的话是 \(\mathcal O(n^3)\) 的，只有 \(20pts\)

有一个规律，就是一个堆的 \(SG\) 值就是这个 \(a_i \% (k+1)\)，之后就可以 \(50pts\) 了。

#include<bits/stdc++.h>
using namespace std;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gec() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
	#define gc() getchar()
	#define scanf ak = scanf
	char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
	class xin_stream{public:template<typename type>xin_stream &operator >> (type &s)
	{
		s = 0; register bool f = 0; register char ch = gc();
		while(!isdigit(ch)) f |= ch == '-',ch = gc();
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 4e3+10,inf = 1e9+10;
#define int long long
namespace xin
{
	int sg[maxn];
	int n,a[maxn],maxx;
	int temp[maxn],zhi = 0;
	bool vis[maxn];
	inline short main()
	{
		file(stone);
		io >> n;
		try(i,1,n) io >> a[i],maxx = max(maxx,a[i]);
		auto check = [](int k) -> bool
		{
//			try(i,1,maxx)
//			{
//				zhi = 0;
//				throw(j,i-1,i-k)
//					if(j < 0) break;
//					else temp[++zhi] = sg[j],vis[sg[j]] = 1;
////				std::sort(temp+1,temp+zhi+1);
//				for(register int j=0;;j++) if(!vis[j]) {sg[i] = j; break;}
//				try(j,1,zhi) vis[temp[j]] = 0;
//			}
			int ret = 0;
			try(i,1,n) ret ^= (a[i] % (k + 1));
//			jb(k);
//			try(i,1,maxx) jb(sg[i]);
			return ret;
		};
		try(i,1,n)
			printf(check(i) ? "Alice " : "Bob ");
		return 0;
	}
}
signed main() {return xin::main();}

黑客1

这个就是垃圾题。

枚举就行了。

然后将两个倍数的区间进行判断就行，其实就是找到交集。。。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gec() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
	#define gc() getchar()
	#define scanf ak = scanf
	char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
	class xin_stream{public:template<typename type>xin_stream &operator >> (type &s)
	{
		s = 0; register bool f = 0; register char ch = gc();
		while(!isdigit(ch)) f |= ch == '-',ch = gc();
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 4e3+10,inf = 1e9+10;
#define int long long
namespace xin
{
	const int mod = 1e9+7;
	int a,b,c,d,jsq,ans;
	inline int gcd(int x,int y) {return !y ? x : gcd(y,x%y);}
	inline short main()
	{
		freopen("hacker.in","r",stdin); freopen("hacker.out","w",stdout);
		io >> a >> b >> c >> d;
		if(b <= 1000 and d <= 1000)
		{
			auto check = [](int x,int y)
			{
				register int yue = gcd(x,y);
				if(yue) x /= yue,y /= yue;
				if(x + y <= 999) return x+y;
				return 0ll;
			};
			try(i,a,b) try(j,c,d)
				jsq += check(i,j),jsq -= (jsq >= mod) ? mod : 0;
			cout<<jsq % mod<<endl;
			return 0;
		}
		int ms1 = std::min(999ll,b),ms2 = std::min(999ll,d);
		try(i,1,ms1) try(j,1,ms2-i)
		if(gcd(i,j) == 1)
		{
			int l1,r1,l2,r2;
			l1 = (a + i - 1) / i; r1 = b / i;
			l2 = (c + j - 1) / j; r2 = d / j;
			if(r1 >= l2 and l1 <= l2 and r2 >= r1)
				ans += (r1 - l2 + 1) * (i + j) % mod,ans %= mod;
			else if(r2 >= l1 and l2 <= l1 and r1 >= r2)
				ans += (r2 - l1 + 1) * (i + j) % mod,ans %= mod;
			else if(r2 >= r1 and l2 <= l1) ans += (r1 - l1 + 1) * (i + j) % mod,ans %= mod;
			else if(r1 >= r2 and l2 >= l1) ans += (r2 - l2 + 1) * (i + j) % mod,ans %= mod;
		}
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

黑客2

垃圾高精，超级卡常，然后使用 \(nb\) 方法可以过掉。。

#include<bits/stdc++.h>
using namespace std;
#define try(i,a,b) for(register int i=a;i<=b;++i)
#define throw(i,a,b) for(register int i=a;i>=b;--i)
#define go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define file(x) FILE *FI = freopen(#x".in","r",stdin); FI = freopen(#x".out","w",stdout);
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<endl
	#define gec() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1 ++
	#define gc() getchar()
	#define scanf ak = scanf
	char buf[1<<20],*p1 = buf,*p2 = buf; using ll = long long; using ull = unsigned long long; int ak;
	class xin_stream{public:template<typename type>xin_stream &operator >> (type &s)
	{
		s = 0; register bool f = 0; register char ch = gc();
		while(!isdigit(ch)) f |= ch == '-',ch = gc();
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,two = 4e3+10,inf = 1e9+10;
int n,m,k;
#define int long long
namespace xin
{
	const ll bse = 1e9;
	struct bigint
	{
		ll a[250];int len;
		bigint(){len = 1;}
		bigint(int x){
			memset(a,0,sizeof(a));len = 1;
			while(x){a[len++] = x % bse,x /= bse;}len --;
		}
		void print(){
			printf("%lld",a[len]);
			for(register int i = len-1 ; i ; i --)printf("%09lld",a[i]);
		}
		void pprint()
		{
			printf("%lld",a[len]);
			throw(i,len-1,1) printf("%017lld",a[i]);
//			printf("%016lld",a[1]);
		}
		friend bigint operator + (const bigint& a,const bigint& b){
			bigint ret = 0; ret.len = max(a.len,b.len) + 1;
			for(register int i = 1 ; i <= ret.len ; i ++)
				ret.a[i] += a.a[i] + b.a[i],
				ret.a[i+1] += ret.a[i] / bse,
				ret.a[i] %= bse;
			for(register int i = 1 ; i <= ret.len ; i ++)
				ret.a[i+1] += ret.a[i] / bse,
				ret.a[i] %= bse;
			while(ret.len > 1 && !ret.a[ret.len]) ret.len --;
			return ret;
		}
		friend bigint operator * (const bigint& a,const bigint& b){
			bigint ret = 0; ret.len = a.len + b.len + 1;
			for(register int i = 1 ; i <= a.len ; i ++)
				for(int j = 1 ; j <= b.len ; j ++)
					ret.a[i+j-1] += a.a[i] * b.a[j],
					ret.a[i+j] += ret.a[i+j-1] / bse,
					ret.a[i+j-1] %= bse;
			for(register int i = 1 ; i <= ret.len ; i ++)
				ret.a[i+1] += ret.a[i] / bse ,
				ret.a[i] %= bse;
			while(ret.len > 1 && !ret.a[ret.len]) ret.len --;
			return ret;
		}
		friend bigint operator * (const bigint& a,const int &b){
			bigint ret = 0 ; ret.len = a.len;
			int x = b;
			while(x) ret.len ++ , x /= bse;
			for(register int i = 1 ; i <= a.len ; i ++)
				ret.a[i] += a.a[i] * b,
				ret.a[i+1] += ret.a[i] / bse,
				ret.a[i] %= bse;
			for(register int i = 1 ; i <= ret.len ; i ++)
				ret.a[i+1] += ret.a[i] / bse,
				ret.a[i] %= bse;
			while(ret.len > 1 && !ret.a[ret.len]) ret.len --;
			return ret;
		}
	};
	bigint ans1 = 0,ans2 = 0,ans = 0,pow2 = 1;
	bool vis[two][two];
	int st[maxn];
	bigint f[130001];
	class xin_data
	{
		public:
			int x,y;
			xin_data(){}
			xin_data(int x,int y):x(x),y(y){}
	}d[two/5][two/5];
	int tot;
	bigint shi[501];
	xin_data dfs(int x,int s)
	{
		if(vis[x][s]) return d[x][s];
		vis[x][s] = 1; 
		if(x == n + 1) return d[x][s] = xin_data(1,0);
		register int temp1 = ++tot,temp2 = ++tot;
		try(i,1,k) if(!(s & (1 << i - 1)))
		{
			xin_data temp = dfs(x+1,s|st[i]);
			f[temp1] = f[temp1] + f[temp.x];
			f[temp2] = f[temp2] + f[temp.y];
			bigint wk = f[temp.x] * i * shi[n-x];
			f[temp2] = f[temp2] + wk;
		}
		return d[x][s] = xin_data(temp1,temp2);
	}
	inline short main()
	{
		try(i,1,m)
		{
			register int x,y; io >> x >> y;
			st[x] |= (1 << y - 1);
		}
		shi[0] = 1;
		try(i,1,500) shi[i] = shi[i-1] * 10;
		f[1] = 1; tot = 1;
		xin_data ans = dfs(1,0);
		f[ans.x].print(); cout<<endl;
		f[ans.y].print(); cout<<endl;
		return 0;
	}
}
#undef int
using namespace std;
namespace xin1
{
	const int maxn = 10100;
	struct bigint
	{
	    int d[maxn], len;
	    void clean() { while(len > 1 && !d[len-1]) len--; }
	    bigint()     { memset(d, 0, sizeof(d)); len = 1; }
	    bigint(int num)   { *this = num; }
	    bigint(char* num) { *this = num; }
	    bigint operator = (const char* num)
		{
	        memset(d, 0, sizeof(d)); len = strlen(num);
	        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
	        clean();
	        return *this;
	    }
	    bigint operator = (int num)
		{
	        char s[21]; sprintf(s, "%d", num);
	        *this = s;
	        return *this;
	    }
	    bigint operator + (const bigint& b){
	        bigint c = *this; int i;
	        for (i = 0; i < b.len; i++){
	            c.d[i] += b.d[i];
	            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
	        }
	        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
	        c.len = max(len, b.len);
	        if (c.d[i] && c.len <= i) c.len = i+1;
	        return c;
	    }
	    bigint operator - (const bigint& b){
	        bigint c = *this; int i;
	        for (i = 0; i < b.len; i++){
	            c.d[i] -= b.d[i];
	            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
	        }
	        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
	        c.clean();
	        return c;
	    }
	    bigint operator * (const bigint& b)const{
	        int i, j; bigint c; c.len = len + b.len;
	        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
	            c.d[i+j] += d[i] * b.d[j];
	        for(i = 0; i < c.len-1; i++)
	            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
	        c.clean();
	        return c;
	    }
	    bigint operator / (const bigint& b){
	        int i, j;
	        bigint c = *this, a = 0;
	        for (i = len - 1; i >= 0; i--)
	        {
	            a = a*10 + d[i];
	            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
	            c.d[i] = j;
	            a = a - b*j;
	        }
	        c.clean();
	        return c;
	    }


	    bool operator <(const bigint& b) const{
	        if(len != b.len) return len < b.len;
	        for(int i = len-1; i >= 0; i--)
	            if(d[i] != b.d[i]) return d[i] < b.d[i];
	        return false;
	    }
	    bool operator >(const bigint& b) const{return b < *this;}


	    std::string str() const{
	        char s[maxn]={};
	        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
	        return s;
	    }
	};

	istream& operator >> (istream& in, bigint& x)
	{
	    std::string s;
	    in >> s;
	    x = s.c_str();
	    return in;
	}

	ostream& operator << (ostream& out, const bigint& x)
	{
	    out << x.str();
	    return out;
	}

	inline short main()
	{
		bigint ans = 0;
		try(i,1,n) ans = ans * 10 + 1;
		ans = ans * (k + 1) * 10;
		ans = ans / 2;
		bigint pow2 = 1;
		try(i,1,n) pow2 = pow2 * k;
		cout<<pow2<<endl;
		ans = ans * pow2;
		cout<<ans / 10<<endl;
		return 0;
	}
}
signed main()
{
	file(hacker2);
	io >> n >> m >> k;
	if(!m) return xin1::main(),0;
	else return xin::main(),0;
}