Graph Automata Player-白红宇

Graph Automata Player

阅读量：5770 次

发布时间：2019-06-18

本文共 3535 字，大约阅读时间需要 11 分钟。

题目

第一道高速幂。同一时候也是第一道高斯消元。

输入的边的关系矩阵就是系数矩阵co

[co] ^ T * [ans]== (当前0时刻的状态)。[co] ^ T可由矩阵高速幂解得

那么-T时刻的状态便是ans矩阵的值。可由高斯消元解得

推断一下就可以

高斯消元中系数矩阵是a[0...n - 1][0...m - 1] 常数矩阵是a[0...n - 1][m]

返回-1表示无解，等于0有唯一解。大于0表示不确定的变量个数

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;//LOOP#define FF(i, a, b) for(int i = (a); i < (b); ++i)#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)//OTHER#define SZ(V) (int)V.size()#define PB push_back#define MP make_pair#define all(x) (x).begin(),(x).end()//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)#define RS(s) scanf("%s", s)//OUTPUT#define WI(n) printf("%d\n", n)#define WS(n) printf("%s\n", n)//debug//#define online_judge#ifndef online_judge#define dt(a) << (#a) << "=" << a << " "#define debugI(a) cout dt(a) << endl#define debugII(a, b) cout dt(a) dt(b) << endl#define debugIII(a, b, c) cout dt(a) dt(b) dt(c) << endl#define debugIV(a, b, c, d) cout dt(a) dt(b) dt(c) dt(d) << endl#define debugV(a, b, c, d, e) cout dt(a) dt(b) dt(c) dt(d) dt(e) << endl#else#define debugI(v)#define debugII(a, b)#define debugIII(a, b, c)#define debugIV(a, b, c, d)#endif#define sqr(x) (x) * (x)typedef long long LL;typedef unsigned long long ULL;typedef vector 
                    
                      VI;const double eps = 1e-9;const int MOD = 1000000007;const double PI = acos(-1.0);//const int INF = 0x3f3f3f3f;const int maxn = 310;const LL INF = 0x3f3f3f3f3f3f3f3fLL;struct Mat{ int n, m; bool v[maxn][maxn]; Mat(int n = 0, int m = 0, int zero = 0) { this->n = n; this->m = m; if (zero) { REP(i, n) REP(j, m) v[i][j] = false; } }};Mat mul(Mat& a, Mat&b){ Mat ret(a.n, b.m, 1); REP(i, a.n) REP(j, b.m) REP(k, a.m) ret.v[i][j] ^= (a.v[i][k] & b.v[k][j]); return ret;}Mat qpow(Mat& a, int b){ Mat ret(a.n, a.m); bool f = 1; while (b) { if (b & 1) { if (f) ret = a, f = 0; else ret = mul(ret, a); } b >>= 1; a = mul(a, a); } return ret;}bool a[maxn][maxn];int gauss(int N, int M){ int r, c, pvt; bool flag; for (r = 0, c = 0; r < N && c < M; r++, c++) { flag = false; for (int i = r; i < N; i++) if (a[i][c]) { flag = a[pvt = i][c]; break; } if (!flag) { r--; continue; } if (pvt != r) for (int j = r; j <= M; j++) swap(a[r][j], a[pvt][j]); for (int i = r + 1; i < N; ++i) { if (a[i][c]) { a[i][c] = false; for (int j = c + 1; j <= M; ++j) if (a[r][j]) a[i][j] = !a[i][j]; } } } for (int i = r; i < N; i++) if (a[i][M]) return -1; if (r < M) return M - r; for (int i = M - 1; i >= 0; i--) { for (int j = i + 1; j < M; j++) if (a[i][j]) a[i][M] ^= a[j][M]; a[i][M] /= a[i][i]; } return 0;}int main(){ int n, T, x; while (~RI(n)) { Mat co(n, n); REP(i, n) REP(j, n) { RI(x); co.v[i][j] = (x == 1 ? true : false); } REP(i, n) { RI(x); a[i][n] = (x == 1 ?

true : false); } RI(T); co = qpow(co, T); REP(i, n) REP(j, n) a[i][j] = co.v[i][j]; int ans = gauss(n, n); if (ans == -1) puts("none"); else if (ans) puts("ambiguous"); else { REP(i, n) printf("%d%c", a[i][n], (i == n - 1 ?

'\n' : ' ')); } } return 0; }

转载地址：http://ijiux.baihongyu.com/

你可能感兴趣的文章

在O(1)时间删除链表结点

查看>>

页面中checkbox返回的是一个数组，如何对数组进行操作

查看>>

Uncaught SyntaxError: Invalid or unexpected token

查看>>

SqlMembershipProvider.CreateUser 方法(测试已通过)

查看>>

ActiveMQ之composite destinations