https://gmoj.net/senior/#contest/show/2989/1
先考虑 n=2 时怎么做, 打表找规律找了半天找不出来.
赛后才知道这是 nim 积.
定义 \(x?y\) 为 \(sg(x,y)\).
有一坨性质:
- \(x,y<2^{
- 2^k
- },x?y<2^{
- 2^k
- }\)
- \(2^{
- 2^k
- }?2^{
- 2^k
- }={
- 3 \over 2
- }2^{
- 2^k
- }\)
可以把? 看做乘法,\(⊕\)(异或) 看做加法, 所以还有分配律.
求 \(x?y(x>y)\), 设 \(k\) 为最大的 \(k\) 满足 \(2^{2^k}<=x\), 设 \(M=2^{2^k}\)
\(x=s*M+t=s*M⊕t,y=p*M+q=p*M⊕q\)
则 \(x?y=spMM+sMq+tpM+tq\)
\(=M(sp+sq+tp)+tq+(M/2?sp)\)
字母间省略了 \(?\) 号,\(+\) 号即 \(⊕\).
递归求出 \(sp,sq,tp,tq,M/2sp\) 即可.
时间复杂度:\(O(5^{log~log~V})\).
预处理 \((0-255,0-255)\) 会快许多.
题目中重定义加法和乘法, 求行列式即可.
注意行列式要逆元,\(v^{-1}=v^{2^{2^k}-2}\)(满足费马小定理).
- Code:
- #include<bits/stdc++.h>
- #define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
- #define ff(i, x, y) for(int i = x, _b = y; i <_b; i ++)
- #define fd(i, x, y) for(int i = x, _b = y; i>= _b; i --)
- #define ll long long
- #define pp printf
- #define hh pp("\n")
- using namespace std;
- #define ul unsigned long long
- const ul maxM = (ul) 1 <<32;
- const ul a2_63 = (ul) 1 << 63;
- const int C = 256;
- ul b[C][C];
- ul calc2(ul x, ul y) {
- if(!x || !y) return 0;
- if(x == 1) return y;
- if(y == 1) return x;
- if(x < y) return calc2(y, x);
- ul M = 2; while(M < maxM && M * M <= x) M *= M;
- ul p = x / M, q = x % M;
- ul s = y / M, t = y % M;
- ul c1 = calc2(p, s), c2 = calc2(p, t) ^ calc2(q, s), c3 = calc2(q, t);
- return M * (c1 ^ c2) ^ c3 ^ calc2(M / 2, c1);
- }
- ul calc(ul x, ul y) {
- if(x < C && y < C) return b[x][y];
- if(x < y) swap(x, y);
- ul M = 2; int k = 1;
- while(M < maxM && M * M <= x) M *= M, k *= 2;
- ul p = x>> k, q = x & (M - 1);
- ul s = y>> k, t = y & (M - 1);
- ul c1 = calc(p, s);
- return ((c1 ^ calc(p, t) ^ calc(q, s)) <<k) ^ calc(q, t) ^ calc(M / 2, c1);
- }
- ul ksm(ul x, ul y) {
- ul s = 1;
- for(; y; y /= 2, x = calc(x, x))
- if(y & 1) s = calc(s, x);
- return s;
- }
- ul qni(ul x) {
- if(x>= maxM) return ksm(x, (a2_63 - 1) * 2);
- ul M = 2; while(M <= x) M *= M;
- return ksm(x, M - 2);
- }
- const int N = 155;
- int n;
- ul a[N][N];
- int main() {
- freopen("partition.in", "r", stdin);
- freopen("partition.out", "w", stdout);
- ff(i, 0, C) ff(j, 0, C) b[i][j] = calc2(i, j);
- scanf("%d", &n);
- fo(i, 1, n) fo(j, 1, n) {
- scanf("%llu", &a[i][j]);
- }
- int ye = 1;
- fo(i, 1, n) {
- int u = -1;
- fo(j, i, n) if(a[j][i])
- u = j;
- if(u == -1) { ye = 0; break;}
- fo(j, i, n) swap(a[u][j], a[i][j]);
- ll v = qni(a[i][i]);
- fo(j, i, n) a[i][j] = calc(a[i][j], v);
- fo(j, i + 1, n) if(a[j][i]) {
- v = a[j][i];
- fo(k, i, n) a[j][k] ^= calc(a[i][k], v);
- }
- }
- pp("%s\n", ye ? "xiaoDyingle" : "xiaoDwandanle");
- }
来源: http://www.bubuko.com/infodetail-3383943.html