Problem
loj 猫锟出的神仙题……流下了不学无术的泪水
Solution
这题是个假的最优化，其实是个计数题
要求权值为
i
i
i 的生成树个数，不妨考虑操作符全部为异或的情况。计数的话还得用Matrix Tree定理，此时矩阵的元素变成了一个桶，且它们的乘法也应该是异或卷积，然而我们并不会定义异或卷积意义下的逆元。
如果我们把桶FWT了，那么FWT后的数组每一位就都是独立的了，这样就可以把每一位单独列成一个矩阵，用Matrix Tree定理即可求出答案数组相应位置的答案。最后把答案数组IFWT一遍即可得到答案数组。
而对于其他的操作符，就在相应的二进制位上采用相应的FWT方式即可。
时间复杂度
O
(
n
3
2
w
+
n
2
w
2
w
)
O(n^32^w+n^2w2^w)
O(n32w+n2w2w)。 算了下感觉跑不过，下了个数据发现跑了13s，于是在求行列式的时候加了个如果对角线上有0就直接返回0之后就只需要跑1.4s了。。感觉有点迷
Code
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std
;
typedef long long ll
;
const int maxn
=5010,mod
=998244353,inv2
=499122177;
template <typename Tp
> inline int getmin(Tp
&x
,Tp y
){return y
<x
?x
=y
,1:0;}
template <typename Tp
> inline int getmax(Tp
&x
,Tp y
){return y
>x
?x
=y
,1:0;}
template <typename Tp
> inline void read(Tp
&x
)
{
x
=0;int f
=0;char ch
=getchar();
while(ch
!='-'&&(ch
<'0'||ch
>'9')) ch
=getchar();
if(ch
=='-') f
=1,ch
=getchar();
while(ch
>='0'&&ch
<='9') x
=x
*10+ch
-'0',ch
=getchar();
if(f
) x
=-x
;
}
int n
,m
,l
,N
,a
[80][80],G
[80][80][maxn
],ans
[maxn
];
char op
[20],s
[maxn
];
int pls(int x
,int y
){return x
+y
>=mod
?x
+y
-mod
:x
+y
;}
int dec(int x
,int y
){return x
<y
?x
-y
+mod
:x
-y
;}
int power(int x
,int y
)
{
int res
=1;
for(;y
;y
>>=1,x
=(ll
)x
*x
%mod
)
if(y
&1)
res
=(ll
)res
*x
%mod
;
return res
;
}
void FWT(int *a
,int f
)
{
for(int i
=1;i
<N
;i
<<=1)
for(int j
=0;j
<N
;j
+=(i
<<1))
for(int k
=0;k
<i
;++k
)
{
if(s
[i
]=='&')
a
[j
+k
]=f
?pls(a
[j
+k
],a
[j
+k
+i
]):dec(a
[j
+k
],a
[j
+k
+i
]);
if(s
[i
]=='|')
a
[j
+k
+i
]=f
?pls(a
[j
+k
],a
[j
+k
+i
]):dec(a
[j
+k
+i
],a
[j
+k
]);
if(s
[i
]=='^')
{
int x
=a
[j
+k
],y
=a
[j
+k
+i
];
a
[j
+k
]=pls(x
,y
);a
[j
+k
+i
]=dec(x
,y
);
if(!f
)a
[j
+k
]=(ll
)a
[j
+k
]*inv2
%mod
,a
[j
+k
+i
]=(ll
)a
[j
+k
+i
]*inv2
%mod
;
}
}
}
void input()
{
int x
,y
,v
;
read(n
);read(m
);scanf("%s",op
+1);
l
=strlen(op
+1);N
=1<<l
;
for(int i
=1;i
<=l
;i
++) s
[1<<(i
-1)]=op
[i
];
for(int i
=1;i
<=m
;i
++)
{
read(x
);read(y
);read(v
);
G
[x
][y
][v
]=dec(G
[x
][y
][v
],1);
G
[y
][x
][v
]=dec(G
[y
][x
][v
],1);
++G
[x
][x
][v
];++G
[y
][y
][v
];
}
}
int gauss()
{
int det
=1,inv
;
for(int i
=1,k
;i
<n
;i
++)
{
if(!a
[i
][i
])
{
k
=0;
for(int j
=i
;j
<n
;j
++) if(a
[j
][i
]){k
=j
;break;}
if(k
==0) return 0;
swap(a
[i
],a
[k
]);
}
det
=(ll
)det
*a
[i
][i
]%mod
;inv
=power(a
[i
][i
],mod
-2);
for(int j
=i
+1;j
<n
;j
++) a
[i
][j
]=(ll
)a
[i
][j
]*inv
%mod
;
for(int j
=i
+1;j
<n
;j
++)
for(int r
=i
+1;r
<n
;r
++)
a
[j
][r
]=dec(a
[j
][r
],(ll
)a
[j
][i
]*a
[i
][r
]%mod
);
}
return det
;
}
int main()
{
input();
for(int i
=1;i
<n
;i
++)
for(int j
=1;j
<=i
;j
++)
{
FWT(G
[i
][j
],1);
if(j
<i
) memmove(G
[j
][i
],G
[i
][j
],sizeof(G
[i
][j
]));
}
for(int s
=0;s
<N
;++s
)
{
for(int i
=1;i
<n
;i
++)
for(int j
=1;j
<n
;j
++)
a
[i
][j
]=G
[i
][j
][s
];
ans
[s
]=gauss();
}
FWT(ans
,0);
for(int i
=N
-1;~i
;i
--) if(ans
[i
]) {printf("%d\n",i
);return 0;}
puts("-1");
return 0;
}
