UVALive 5879 - Boring Card Game （解模线性方程，暴力枚举）

UVALive5879 题意：就是规定了一个发牌和收牌的规则。总共N个人玩游戏，有5*N张牌（分别是1,2,….5N）, 按照规则发牌，如果有一个人拿到了1,2,3,4,5的牌，这个人就赢了，否则进行收牌，然后再来。要预测是第几个人赢，，以及第几次赢。就是发牌规则和收牌规则得到一个映射关系，这其实是一个置换群。然后就可以暴力枚举5张牌的位置，以及哪个人赢。之后就解一个模线性方程组了。卧槽！竟然没看出来这其实是置换群，这样就是一个一个环组成。我还n^2去找然后TLE。弱！

#include <stdio.h>

#include

#include <string.h>

#include

#include <math.h>
using namespace std;
namespace ME{
long long extend_gcd(long long a,long long b,long long &x,long long &y){
if(a == 0 && b == 0)return -1;
if(b == 0){x = 1; y = 0; return a;}
long long d = extend_gcd(b,a%b,y,x);
y -= a/bx;
return d;
}
long long m[10],a[10];
bool solve(long long &m0,long long &a0,int m,int a){
long long y,x;
long long g = extend_gcd(m0,m,x,y);
if(abs(a-a0)%g)return false;
x = (a-a0)/g;
x %= m/g;
a0 = (xm0 + a0);
m0 = m/g;
a0 %= m0;
if(a0 < 0)a0 += m0;
return true;
}
bool MLES(long long &m0,long long &a0,int n){
bool flag = true;
m0 = 1;
a0 = 0;
for(int i = 0;i < n;i++){
if(!solve(m0,a0,m[i],a[i])){
flag = false;
break;
}
}
return flag;
}
};

const int MAXN = 5010;
int link[MAXN];
int a[MAXN];
int b[MAXN];
int belong[MAXN];
int pe[MAXN];
int id[MAXN];
long long ans[MAXN];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1 && n){
for(int i = 1;i <= 5n;i++)scanf(“%d”,&a[i]);
for(int i = 1;i <= 5n;i++)b[a[i]] = i;
for(int i = 1;i <= n;i++){
link[2(i-1)+1] = 5(i-1)+1;
link[2(i-1)+2] = 5(i-1)+2;
link[2*n + 2*(i-1)+1] = 5(i-1)+3;
link[2\n + 2*(i-1)+2] = 5(i-1)+4;
link[4\n + (i-1) + 1] = 5*(i-1)+5;
}
memset(belong,-1,sizeof(belong));
for(int i = 1;i <= 5n;i++){
if(belong[i] != -1)continue;
int u = i;
int cnt = 0;
while(belong[u] == -1){
belong[u] = i;
id[u] = cnt;
cnt++;
u = link[u];
}
pe[i] = cnt;
for(int j = link[i];j != i;j = link[j])
pe[j] = cnt;
}
memset(ans,-1,sizeof(ans));
for(int i = 1;i <= n;i++){
int c[10];
c[1] = 2(i-1)+1;
c[2] = 2(i-1)+2;
c[3] = 2\n + 2*(i-1)+1;
c[4] = 2*n + 2*(i-1)+2;
c[5] = 4*n + i;
do{
bool flag = true;
for(int j = 1;j <= 5;j++){
if(belong[b[j]] != belong[c[j]]){
flag = false;
break;
}
}
if(!flag)continue;
for(int j = 1;j <= 5;j++){
ME::m[j-1] = pe[b[j]];
ME::a[j-1] = (id[c[j]] - id[b[j]] + pe[b[j]])%pe[b[j]];
}
long long m0,a0;
if(!ME::MLES(m0,a0,5))continue;
if(ans[i] == -1)ans[i] = a0;
else if(ans[i] > a0)ans[i] = a0;

        }
        while(next_permutation(c+1,c+6));
    }
    long long Min = -1;
    int id  = -1;
    for(int i = 1;i <= n;i++){
        if(ans\[i\] == -1)continue;
        if(Min == -1 || Min > ans\[i\]){
            Min = ans\[i\];
            id = i;
        }
    }
    if(id == -1)printf("Neverending game.\\n");
    else printf("Player %d wins game number %lld.\\n",id,ans\[id\]+1);
}
return 0;

}