首页 > 代码库 > ASC #1
ASC #1
开始套题训练，第一套ASC题目，记住不放过每一题，多独立思考。
Problem A ZOJ 2313 Chinese Girls‘ Amusement 循环节
题意：给定n，为圆环长度，求k <= n/2,从1出发，每次顺时针方向走k步，即1->k+1->2*k+1,直到遇到一个已经走过的点结束，要求最终把所有点访问一遍，最后回到1，使得k尽量大。
代码：
Problem B ZOJ 2314 Reactor Cooling 无源汇上下界网络流
题意：经典题，有上下界无源无汇的可行流，对于每条边u->v，上界流量C(u,v),下界流量B(u, v)，可以这样构图，建立附加源点S，T对于每条边u->v，在流量图中连一条容量为C(u, v)-B(u, v)的边，同时S->v连容量B(u, v) 的边，u->T连B(u, v) 的边，跑一遍网络流，当从S出发的边满流时，有可行流，原图中每条边流量为相应B(u, v)+最大流图中流量g(u, v).
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pb push_back 9 #define in freopen("solve_in.txt", "r", stdin); 10 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 11 #define inf 0x0f0f0f0f 12 using namespace std; 13 typedef long long LL; 14 typedef map<int, int> MPS; 15 typedef pair<int, int> PII; 16 const int maxn = 222; 17 struct Node { 18 int c, l, id; 19 Node() {} 20 Node(int c, int l, int id):c(c), l(l), id(id) {} 21 }; 22 vector<Node> cap; 23 24 25 struct Edge { 26 int u, v, c; 27 Edge(int u, int v, int c):u(u), v(v), c(c) {} 28 }; 29 struct Max_flow { 30 int n, m; 31 int src, sink; 32 vector<Edge> edges; 33 vector<int> G[maxn]; 34 int Now[maxn], Dfn[maxn], cur[maxn]; 35 void init(int n) { 36 this->n = n; 37 for(int i = 0; i < n; i++) G[i].clear(); 38 edges.clear(); 39 } 40 void add(int u, int v, int c) { 41 edges.pb(Edge(u, v, c)); 42 edges.pb(Edge(v, u, 0)); 43 m = edges.size(); 44 G[u].pb(m-2); 45 G[v].pb(m-1); 46 } 47 int ISAP(int s, int flow) { 48 if(s == sink) 49 return flow; 50 int i, tab = n, vary, now = 0; 51 int p = cur[s]; 52 do { 53 Edge &e = edges[G[s][cur[s]]]; 54 if(e.c > 0) { 55 if(Dfn[s] == Dfn[e.v]+1) 56 vary = ISAP(e.v, min(flow-now, e.c)), 57 now += vary, e.c -= vary, edges[G[s][cur[s]]^1].c += vary; 58 if(Dfn[src] == n) 59 return now; 60 if(e.c > 0) tab = min(tab, Dfn[e.v]); 61 if(flow == now) 62 break; 63 } 64 cur[s]++; 65 if(cur[s] == (int)G[s].size()) cur[s] = 0; 66 } while(p != cur[s]); 67 if(now == 0) { 68 if(--Now[Dfn[s]] == 0) 69 Dfn[src] = n; 70 Now[Dfn[s] = tab+1]++; 71 } 72 return now; 73 } 74 int max_flow(int src, int sink) { 75 this->src =http://www.mamicode.com/ src; 76 this->sink = sink; 77 int flow = 0; 78 memset(Dfn, 0, sizeof Dfn); 79 memset(Now, 0, sizeof Dfn); 80 memset(cur, 0, sizeof cur); 81 Now[0] = n; 82 for(; Dfn[src] < n;) 83 flow += ISAP(src, inf); 84 return flow; 85 } 86 } mc; 87 vector<int> mx; 88 89 int main() { 90 91 int T; 92 for(int t = scanf("%d", &T); t <= T; t++) { 93 int n, m; 94 cap.clear(); 95 mx.clear(); 96 97 scanf("%d%d", &n, &m); 98 mc.init(n+2); 99 int src = http://www.mamicode.com/n, sink = n+1;100 101 for(int i = 1; i <= m; i++) {102 int u, v, c, l;103 scanf("%d%d%d%d", &u, &v, &l, &c);104 u--, v--;105 mc.add(u, v, c-l);106 int tmp = mc.edges.size()-2;107 cap.pb(Node(c, l, tmp));108 mc.add(src, v, l);109 tmp = mc.edges.size()-2;110 mx.pb(tmp);111 mc.add(u, sink, l);112 }113 int flow = mc.max_flow(src, sink);114 //// cout << flow << endl;115 int ok = 1;116 for(int i = 0; i < (int)mx.size(); i++) {117 int id = mx[i];118 if(mc.edges[id].c) {119 ok = 0;120 break;121 }122 }123 124 if(t != 1) puts("");125 if(ok) {126 puts("YES");127 for(int i = 0; i < (int)cap.size(); i++) {128 Node x = cap[i];129 int id = x.id;130 printf("%d\n", x.c-mc.edges[id].c);131 }132 } else puts("NO");133 }134 return 0;135 }
关于上下界网络流补充资料：http://blog.sina.com.cn/s/blog_76f6777d0101bara.html
Problem C ZOJ 2315 New Year Bonus Grant 树形dp或贪心
题意：以1为根的树中，每个结点可以从父节点获得一个奖励，或者自己给其中一个子节点的奖励，或者既不获得也不给出奖励。求所有结点获得的最大奖励数目
分析：我是用树形dp做的，dp[u][i]，i为1表示从父亲结点获得奖励时该子树最大奖励和，dp[u][0]为不从父节点获得奖励时该子树的最大奖励和。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pb push_back 9 #define in freopen("solve_in.txt", "r", stdin);10 #define bug(x) printf("Line : %u >>>>>>\n", (x));11 #define inf 0x0f0f0f0f12 using namespace std;13 typedef long long LL;14 typedef map<int, int> MPS;15 typedef pair<int, int> PII;16 const int maxn = (int)5e5 + 100;17 vector<int> g[maxn];18 int dp[maxn][2], pa[maxn];19 void dfs(int u, int fa) {20 int sum = 0;21 dp[u][0] = dp[u][1] = -1;22 pa[u] = -1;23 for(int i = 0; i < sz(g[u]); i++) {24 int v = g[u][i];25 if(v == fa) continue;26 dfs(v, u);27 sum += dp[v][0];28 }29 dp[u][1] = 1 + sum;30 dp[u][0] = sum;31 for(int i = 0; i < sz(g[u]); i++) {32 int v = g[u][i];33 if(v == fa) continue;34 if(sum-dp[v][0]+dp[v][1] > dp[u][0])35 dp[u][0] = sum-dp[v][0]+dp[v][1], pa[u] = v;36 }37 }38 vector<int> ans;39 void printAns(int u, int st, int fa) {40 if(st) ans.pb(u);41 for(int i = 0; i < sz(g[u]); i++) {42 int v = g[u][i];43 if(v == fa) continue;44 printAns(v, v == pa[u] && !st, u);45 }46 }47 int main() {48 49 int T;50 for(int t = scanf("%d", &T); t <= T; t++) {51 if(t != 1) puts("");52 int n;53 ans.clear();54 scanf("%d", &n);55 for(int i = 1; i <= n; i++) g[i].clear();56 for(int i = 1; i < n; i++) {57 int u;58 scanf("%d", &u);59 g[u].pb(i+1);60 }61 dfs(1, 0);62 printf("%d\n", 1000*dp[1][0]);63 printAns(1, 0, 0);64 sort(ans.begin(), ans.end());65 for(int i = 0; i < (int)ans.size(); i++) {66 printf("%d%c", ans[i], i == (int)ans.size()-1 ? ‘\n‘ : ‘ ‘);67 }68 }69 return 0;70 }
Problem D ZOJ 2316 Matrix Multiplication 顶点度数
题意：给定一个图，n个顶点，m条边，最终就是要你求每个点度数平方之和。
分析：注意防止溢出。
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pb push_back 9 #define in freopen("solve_in.txt", "r", stdin);10 #define bug(x) printf("Line : %u >>>>>>\n", (x));11 #define inf 0x0f0f0f0f12 using namespace std;13 typedef long long LL;14 typedef map<int, int> MPS;15 MPS mps;16 17 const int maxn = 10000 + 100;18 int num[maxn];19 int cnt;20 21 int idx(int x){22 if(mps.count(x) == false)23 mps[x] = ++cnt;24 return mps[x];25 }26 int main(){27 28 int T;29 for(int t = scanf("%d", &T); t <= T; t++){30 memset(num, 0, sizeof num);31 int n, m;32 mps.clear();33 cnt = 0;34 scanf("%d%d", &n, &m);35 for(int i = 1; i <= m; i++){36 int u, v;37 scanf("%d%d", &u, &v);38 u = idx(u);39 v = idx(v);40 num[u]++, num[v]++;41 }42 LL ans = 0;43 for(int i = 1; i <= n;i++){44 ans += (LL)num[i]*num[i];45 }46 if(t != 1) puts("");47 printf("%lld\n", ans);48 }49 return 0;50 }
Problem E ZOJ 2317 Nice Patterns Strike Back 矩阵快速幂，组合数
题意：一个n*m的方格，每个格子有两种颜色，现在给整个方格涂色，要求一个2*2的正方形内颜色不能相同，问有多少种颜色，m<=5, n <= 10^100，最终结果模p，p <= 10000。
分析：由于能否构成同样颜色正方形取决于当前列连续2格以及前一列的对应两列是否颜色一样，所以对每列的状态，st看能从哪些状态st‘转移过来。这样可以建立一个转移图
边u->v表示前一列状态为u下列可为v。dp[i+1][u] = sum{dp[i][v]}，可以得到一个矩阵，g[v][u]表示v转移到u，那么答案就是g^n然后取结果矩阵sum{g[i][0]}之和。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 #include <cstring> 5 #include <vector> 6 #include <cmath> 7 #include <cassert> 8 #include <algorithm> 9 #define pb push_back 10 #define mp make_pair 11 #define esp 1e-8 12 #define lson l, m, rt<<1 13 #define rson m+1, r, rt<<1|1 14 #define sz(x) ((int)((x).size())) 15 #define pb push_back 16 #define in freopen("solve_in.txt", "r", stdin); 17 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 18 #define inf 0x0f0f0f0f 19 using namespace std; 20 typedef long long LL; 21 typedef map<int, int> MPS; 22 typedef pair<int, int> PII; 23 24 const int maxn = 111; 25 const int maxm = 44; 26 const int B = 10000; 27 int m, p; 28 29 struct BigInt { 30 int dig[maxn], len; 31 BigInt(int num = 0):len(!!num) { 32 memset(dig, 0, sizeof dig); 33 dig[0] = num; 34 } 35 int operator [](int x)const { 36 return dig[x]; 37 } 38 int& operator [](int x) { 39 return dig[x]; 40 } 41 BigInt normalize() { 42 while(len && dig[len-1] == 0) len--; 43 return *this; 44 } 45 void output() { 46 if(len == 0) { 47 puts("0"); 48 return; 49 } 50 printf("%d", dig[len-1]); 51 for(int i = len-2; i >= 0; i--) 52 printf("%04d", dig[i]); 53 puts(""); 54 } 55 }; 56 BigInt operator / (BigInt a, int b) { 57 BigInt c; 58 c.len = a.len; 59 for(int i = a.len-1, delta = 0; i >= 0; i--) { 60 delta = delta*B+a[i]; 61 c[i] = delta/b; 62 delta %= b; 63 } 64 return c.normalize(); 65 } 66 bool operator == (const BigInt &a, const BigInt &b) { 67 if(a.len != b.len) return false; 68 for(int i = a.len-1; i >= 0; i--) if(a[i] != b[i]) return false; 69 return true; 70 } 71 struct Matrix { 72 int a[maxm][maxm]; 73 Matrix() { 74 memset(a, 0, sizeof a); 75 } 76 }; 77 Matrix operator * (const Matrix &a, const Matrix &b) { 78 Matrix c; 79 for(int i = 0; i < (1<<m)+1; i++) for(int j = 0; j < (1<<m)+1; j++) { 80 for(int k = 0; k < (1<<m)+1; k++) 81 c.a[i][j] = (c.a[i][j] + (LL)a.a[i][k]*b.a[k][j]%p)%p; 82 } 83 return c; 84 } 85 char s[111]; 86 int b[] = {1, 10, 100, 1000}; 87 88 bool check(int x, int y) { 89 for(int i = 0; i < m-1; i++) { 90 if((((x>>i)&1) && ((x>>(i+1))&1) 91 && ((y>>i)&1) && ((y>>(i+1))&1)) || (!((x>>i)&1) && !((x>>(i+1))&1) 92 && !((y>>i)&1) && !((y>>(i+1))&1))) 93 return false; 94 } 95 return true; 96 } 97 int main() { 98 99 100 int T;101 for(int t = scanf("%d", &T); t <= T; t++) {102 if(t != 1) puts("");103 scanf("%s%d%d", s, &m, &p);104 int len = strlen(s);105 BigInt c;106 for(int i = len-1; i >= 0; i--) {107 c[(len-1-i)/4] += b[(len-1-i)%4]*(s[i]-‘0‘);108 c.len = max(c.len, (len-1-i)/4+1);109 }110 Matrix res, g;111 for(int i = 0; i < maxm; i++) for(int j = 0; j < maxm; j++) res.a[i][j] = i == j;112 for(int i = 0; i < (1<<m); i++) {113 g.a[i+1][0] = 1;114 for(int j = 0; j < (1<<m); j++) if(check(i, j)) {115 g.a[j+1][i+1] = 1;116 }117 }118 while(c.len) {119 if(c[0]&1) res = res*g;120 g = g*g;121 c = c/2;122 }123 int ans = 0;124 for(int i = 1; i <= (1<<m); i++)125 ans = (ans + res.a[i][0])%p ;126 printf("%d\n", ans);127 }128 return 0;129 }
一个升级版的题目，不过要用到中国剩余定理：
hdu 4878 ZCC loves words AC自动机+中国剩余定理+快速幂
Problem F ZOJ 2318 Get Out! 有向角度判别法，spfa判负环
题意：给定一些圆，然后自己也是一个圆能否从中突出重围。
分析：将自己的半径加到其他圆上面，并平移坐标系以自己所在坐标为原点，将相交的圆心连一条边，然后问题变成了，看是否有一个多边形包围原点。利用有向视角判别法，每条边两个顶点与原点构成的角度a作为权值，对应原来的边建图，两条有向边，权值对应为a和-a。这样就看原图是否有负环了。利用spfa判别就行。位于多边形外面时显然角度和位0。内部则为360或-360度
注意：本题分析显然不会位于多边形顶点或边界上面，否则可能会出错？spfa判别法注意精度。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 #include <cstring> 5 #include <vector> 6 #include <cmath> 7 #include <cassert> 8 #include <algorithm> 9 #include <queue> 10 #define pb push_back 11 #define mp make_pair 12 #define esp 1e-8 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 #define sz(x) ((int)((x).size())) 16 #define pf(x) ((x)*(x)) 17 #define pb push_back 18 #define in freopen("solve_in.txt", "r", stdin); 19 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 20 #define inf 0x0f0f0f0f 21 using namespace std; 22 typedef long long LL; 23 typedef map<int, int> MPS; 24 typedef pair<int, int> PII; 25 26 const int maxn = 333; 27 double x[maxn], y[maxn], r[maxn], len[maxn]; 28 29 struct Edge { 30 int u, v; 31 double w; 32 Edge() {} 33 Edge(int u, int v, double w):u(u), v(v), w(w) {} 34 }; 35 vector<Edge> edges; 36 vector<int> g[maxn]; 37 int n, m; 38 39 void init() { 40 edges.clear(); 41 for(int i = 0; i < maxn; i++) g[i].clear(); 42 } 43 void add(int u, int v, double w) { 44 edges.pb(Edge(u, v, w)); 45 m = edges.size(); 46 g[u].pb(m-1); 47 } 48 inline bool check(double x1, double y1, double x2, double y2) { 49 return (x1*y2-y1*x2) >= 0; 50 } 51 int inq[maxn]; 52 double dist[maxn]; 53 int cnt[maxn]; 54 55 bool spfa() { 56 queue<int> q; 57 memset(inq, 0, sizeof inq); 58 for(int i = 1; i <= n; i++) { 59 inq[1] = 1; 60 cnt[i] = 0; 61 dist[i] = 0; 62 q.push(i); 63 } while(q.size()) { 64 int u = q.front(); 65 q.pop(); 66 inq[u] = 0; 67 for(int i = 0; i < sz(g[u]); i++) { 68 Edge e = edges[g[u][i]]; 69 int v = e.v; 70 double c = e.w; 71 if(dist[v] > dist[u] + c + esp) { 72 if(dist[v] = dist[u] + c, !inq[v]) { 73 q.push(v); 74 inq[v] = 1; 75 if(++cnt[v] > n + 10) { 76 return true; 77 } 78 } 79 } 80 } 81 } 82 return false; 83 } 84 int main() { 85 86 int T; 87 for(int t = scanf("%d", &T); t <= T; t++) { 88 if(t != 1) puts(""); 89 init(); 90 for(int i = scanf("%d", &n); i <= n+1; i++) { 91 scanf("%lf%lf%lf", x+i, y+i, r+i); 92 } 93 for(int i = 1; i <= n; i++) { 94 x[i] -= x[n+1]; 95 y[i] -= y[n+1]; 96 len[i] = sqrt(pf(x[i])+pf(y[i])); 97 r[i] += r[n+1]; 98 } 99 for(int i = 1; i <= n; i++)100 for(int j = i+1; j <= n; j++) {101 if(sqrt(pf(x[i]-x[j]) + pf(y[i]-y[j])) >= r[i]+r[j])102 continue;103 double ang = acos((x[i]*x[j]+y[i]*y[j])/len[i]/len[j]);104 bool ok = check(x[i], y[i], x[j], y[j]);105 add(i, j, ok ? ang : -ang);106 add(j, i, ok ? -ang : ang);107 }108 if(spfa())109 puts("NO");110 else puts("YES");111 }112 return 0;113 }
Problem G ZOJ 2319 Beautiful People LIS
题意：有n个元素，每个元素是一个对数ai,bi，然后从中选出一些元素，能够排成一列ai < ai+1, 且bi < bi+1,问最长选出多少个元素。
分析：看上去像是LIS，其实也是利用这个，由于ai肯定是单调递增的，所以先按ai小到大排序，bi从大到小排序，然后只要按照bi选出LIS就行了。利用O(nlogn)的经典做法可做。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pb push_back 9 #define in freopen("solve_in.txt", "r", stdin);10 #define bug(x) printf("Line : %u >>>>>>\n", (x));11 #define inf 0x0f0f0f0f12 using namespace std;13 typedef long long LL;14 typedef map<int, int> MPS;15 typedef pair<int, int> PII;16 17 const int maxn = (int)1e5 + 100;18 int f[maxn], dp[maxn];19 MPS mps;20 21 struct Node {22 int s, b, id;23 Node() {}24 Node(int s, int b, int id):s(s), b(b), id(id) {}25 bool operator < (const Node &rhs)const {26 if(s != rhs.s) return s < rhs.s;27 return b > rhs.b;28 }29 } a[maxn];30 int g[maxn];31 int cnt;32 int idx(int x) {33 if(mps.count(x) == false)34 mps[x] = ++cnt;35 return mps[x];36 }37 38 int main() {39 40 int T;41 for(int t = scanf("%d", &T); t <= T; t++) {42 int n;43 cnt = 0;44 if(t != 1) puts("");45 scanf("%d", &n);46 mps.clear();47 for(int i = 1; i <= n; i++) {48 scanf("%d%d", &a[i].s, &a[i].b);49 //// a[i].s = idx(a[i].s);50 //// a[i].b = idx(a[i].b);51 a[i].id = i;52 }53 memset(dp, 0, sizeof dp);54 sort(a+1, a+n+1);55 memset(f, 0x7f, sizeof f);56 int ans = 0, u;57 for(int i = 1; i <= n; i++) {58 int k = lower_bound(f+1, f+n+1, a[i].b)-f-1;59 if(ans < k+1)60 ans = k+1, u = i;61 f[k+1] = a[i].b;62 g[k+1] = i;63 dp[i] = g[k];64 }65 cout << ans << endl;66 int ok = 0;67 while(u) {68 if(ok) cout << ‘ ‘;69 else ok ^= 1;70 cout << a[u].id;71 u = dp[u];72 }73 puts("");74 }75 return 0;76 }
Problem H ZOJ 2320 Cracking‘ RSA 高斯消元
题意：给定m个数，其素因子来自前t个素数，m <= 100，t <= 100。求m个数构成的集合，从中选出一些数构成子集，所有元素之积为完全平方数。有多少种方案。
分析：考虑每个数有选和不选两种状态，用未知量xi表示，由于最终选出来的数的积为完全平方数，所以其乘积中，对于前t个素数的数目必须为偶数个，即模2为0。
所以容易建立t个方程，对每个数分解质因数，质因数个数模2为0，这是一个线性方程组，方程一定有解，所以设自由元个数n，答案2^n-1，这里要用到大数。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 5 #include <cstring> 6 #include <vector> 7 #include <cmath> 8 #include <cassert> 9 #include <algorithm> 10 #define pb push_back 11 #define mp make_pair 12 #define esp 1e-8 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 #define sz(x) ((int)((x).size())) 16 #define pb push_back 17 #define in freopen("solve_in.txt", "r", stdin); 18 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 19 #define inf 0x0f0f0f0f 20 using namespace std; 21 typedef long long LL; 22 typedef map<int, int> MPS; 23 typedef pair<int, int> PII; 24 25 const int maxn = 110; 26 const int B = 10000; 27 28 int num[maxn][maxn], prime[maxn], vis[2222]; 29 int a[maxn][maxn]; 30 void seivePrime() { 31 int tot = 0; 32 for(int i = 2; i < 2000; i++) { 33 if(!vis[i]) prime[++tot] = i; 34 35 for(int j = 1; j <= tot; j++){ 36 if(prime[j]*i >= 2000) break; 37 vis[i*prime[j]] = 1; 38 if(i%prime[j] == 0) break; 39 } 40 if(tot >= 150) break; 41 } 42 } 43 int n, m; 44 void getFact(int b, LL x) { 45 for(int i = 1; i <= n; i++) { 46 if(x%prime[i] == 0) { 47 while(x%prime[i] == 0) { 48 num[b][i-1]++; 49 x /= prime[i]; 50 } 51 if(x == 1) 52 break; 53 } 54 } 55 } 56 int Gauss(int equ, int var) { 57 int k, r, col; 58 for(k = col = 0; k < equ && col < var; k++, col++) { 59 r = k; 60 for(int i = k+1; i < equ; i++) if(a[i][col]) { 61 r = i; 62 break; 63 } 64 if(r != k) for(int i = col; i <= var; i++) 65 swap(a[r][i], a[k][i]); 66 if(a[k][col] == 0) { 67 k--; 68 continue; 69 } 70 for(int i = k+1; i < equ; i++) if(a[i][col]) 71 for(int j = col; j <= var; j++) 72 a[i][j] ^= a[k][j]; 73 } 74 return var-k; 75 } 76 struct BigInt { 77 int dig[maxn], len; 78 BigInt(int num = 0):len(!!num) { 79 memset(dig, 0, sizeof dig); 80 dig[0] = num; 81 } 82 int operator [](int x)const { 83 return dig[x]; 84 } 85 int &operator [](int x) { 86 return dig[x]; 87 } 88 BigInt normalize() { 89 while(len > 1 && dig[len-1] == 0) len--; 90 return *this; 91 } 92 void output() { 93 printf("%d", dig[len-1]); 94 for(int i = len-2; i >= 0; i--) 95 printf("%04d", dig[i]); 96 puts(""); 97 } 98 }; 99 BigInt operator - (BigInt a, int b) {100 BigInt c;101 c.len = a.len;102 for(int i = 0, delta = -b; i < a.len; i++) {103 c[i] = delta+a[i];104 delta = 0;105 if(c[i] < 0) {106 delta = -1;107 c[i] = c[i]+B;108 }109 }110 return c.normalize();111 }112 BigInt operator *(BigInt a, BigInt b) {113 BigInt c;114 c.len = a.len+b.len+1;115 for(int i = 0; i < a.len; i++)116 for(int j = 0, delta = 0; j <= b.len; j++) {117 delta += (c[i+j]+a[i]*b[j]);118 c[i+j] = delta%B;119 delta /= B;120 }121 return c.normalize();122 }123 void print(int x){124 int i , len = 1 , ans[100];125 memset(ans,0,sizeof(ans));126 ans[1] = 1;127 while (x--){128 for (i=1;i<=len;++i) ans[i]*=2;129 for (i=1;i<=len;++i)130 ans[i+1] += ans[i]/10 , ans[i] %= 10;131 if (ans[len+1]) ++len;132 }133 --ans[1];134 for (i=len;i>=1;--i) printf("%d",ans[i]);135 puts("");136 }137 int main() {138 139 int T;140 seivePrime();141 for(int t = scanf("%d", &T); t <= T; t++) {142 if(t != 1) puts("");143 memset(num, 0, sizeof num);144 memset(a, 0, sizeof a);145 scanf("%d%d", &n, &m);146 for(int i = 0; i < m; i++) {147 int x;148 scanf("%d", &x);149 for(int ii = 1; ii <= n; ii++) {150 if(x%prime[ii] == 0) {151 while(x%prime[ii] == 0) {152 a[ii-1][i] ^= 1;153 x /= prime[ii];154 }155 }156 }157 }158 int vary = Gauss(n, m);159 if(vary == 0) puts("0");160 else161 print(vary);162 }163 return 0;164 }
ASC #1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。