题目
描述
\(0-n-1\)的图，满足\(n\)是\(2\)的整数次幂， $ i \to j $ 有 $ A_{i,j} $ 条路径；
一条路径的愉悦值定义为起点和终点编号的\(and\)值;
可以走多条路径；
询问对于\(x \in [1,m] \ , \ y \in [0,n)\)，总步数为\(x\)，所有路径愉悦值\(and\)和为\(y\)的方案数；
你只需要输出他们的异或值；
范围
$n\le 64 \ , \ m \le 20000 $;
题解
令\(w_{i,j}\)为\(i\)步值为\(j\)的方案，做\(fmt\);
根据\(w_{i,j}\)得出\(H_{i,j}\)表示\(and\)值为\(i\)，步数为\(j\)的方案数；
可以用多项式求逆求出\(1 + H_{i} + H_{i}^2 + \cdots = \frac{1}{1-H_{i}}\);
取前\(m\)项得到答案的\(w_{i,j}\)再\(ifmt\);
求\(w_{i,j}\)需要求\(A^i\)；
直接用矩阵乘法求$ A^i $是 $ n^3m $ 的；
考虑\(Q_S(A^i)\)为\(A^i\)中\(and\)值为\(S\)的方案数；
运算满足定律：
$Q_S(A+B) \ = \ Q_S(A) \ + \ Q_S(B) $ ;
\(Qs(kA) \ = \ k \ Q_S(A)\);
根据\(Cayley-Hamilton\)，令\(k = rk(A)\) ;
设\(A\)的特征多项式为：\(F(x)\)
-
对于任意正常数\(w\)都有:
\[\begin{align}
\sum_{i=0}^{k} a_iA_i = 0 \\
\sum_{i=0}^{k} a_iA^{i+w} = 0\\
Q_S(\sum_{i=0}^{k} a_iA^{i+w}) = 0\\
\sum_{i=0}^{k} a_i \ Q_S(A^{i+w}) = 0\\
\end{align}
\] 这启示我们在\(Q_S(A^i)\)中存在一个\(k \le n\)阶的齐次递推；
-
所以只要\(O(n^4)\)求出前\(n+1\)项高斯消元解出\(a_i\)就可以递推\(Q_S\)；
#include<bits/stdc++.h>
#define mod 998244353
#define ll long long
using namespace std;
const int M=80010,N=110;
int n,m,l,r,a[N][N],b[N][N],c[N][N],w[M][N],f[N],h[N][M],g[N][M],len,L,rev[M];
char gc(){
static char*p1,*p2,s[1000000];
if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x=0;char c=gc();
while(c<'0'||c>'9')c=gc();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
return x;
}
int pw(int x,int y){
int re=1;
if(y<0)y+=mod-1;
while(y){
if(y&1)re=(ll)re*x%mod;
y>>=1;x=(ll)x*x%mod;
}
return re;
}
void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
void dec(int&x,int y){x-=y;if(x<0)x+=mod;}
void fmt(int*A,int l,int F){
if(~F){
for(int i=0;i<l;++i)
for(int j=(1<<l)-1;j>=1<<i;--j)if(j>>i&1)inc(A[j^(1<<i)],A[j]);
return ;
}
for(int i=0;i<l;++i)
for(int j=1<<i;j<1<<l;++j)if((j>>i)&1)dec(A[j^(1<<i)],A[j]);
}
void mul(int A[N][N],int B[N][N],int n){
static int tmp[N][N];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
tmp[i][j]=0;
for(int k=0;k<n;++k)inc(tmp[i][j],(ll)A[i][k]*B[k][j]%mod);
}
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)A[i][j]=tmp[i][j];
}
void gauss(int A[N][N],int n){
for(int i=0;i<n;++i){
int pos;for(pos=i;pos<=n&&!A[pos][i];++pos);
if(pos!=i)for(int j=i;j<=n;++j)swap(A[i][j],A[pos][j]);
int iv=pw(A[i][i],mod-2);
for(int j=i;j<=n;++j)A[i][j]=(ll)A[i][j]*iv%mod;
for(int j=0;j<n;++j)if(i!=j)
for(int k=n;k>=i;--k)dec(A[j][k],(ll)A[j][i]*A[i][k]%mod);
}
for(int i=0;i<n;++i)f[i+1]=A[i][n];
}
const int G=3;
void ntt(int*A,int len,int F){
for(L=0;1<<L<len;++L);
for(int i=0;i<len;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
if(i<rev[i])swap(A[i],A[rev[i]]);
}
for(int i=1;i<len;i<<=1){
int wn=pw(G,F*(mod-1)/(i<<1));
for(int j=0;j<len;j+=i<<1){
int w=1;
for(int k=0;k<i;++k,w=(ll)w*wn%mod){
int x=A[j+k],y=(ll)w*A[j+k+i]%mod;
A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
}
}
}
if(!~F){
int iv=pw(len,mod-2);
for(int i=0;i<len;++i)A[i]=(ll)A[i]*iv%mod;
}
}
void cpy(int*A,int*B,int l){for(int i=0;i<l;++i)A[i]=B[i];}
void cls(int*A,int l,int r){for(int i=l;i<r;++i)A[i]=0;}
void inv(int*A,int*B,int l){
if(l==0){B[0]=1;return;}
static int t[M];
inv(A,B,l>>1);
int len=l<<1;
cpy(t,A,l);cls(t,l,len);
ntt(t,len,1);ntt(B,len,1);
for(int i=0;i<len;++i)B[i]=(ll)B[i]*(2-(ll)t[i]*B[i]%mod+mod)%mod;
ntt(B,len,-1);cls(B,l,len);
}
int main(){
freopen("bai.in","r",stdin);
freopen("bai.out","w",stdout);
n=rd();m=rd();
for(l=0;1<<l<n;++l);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)a[i][j]=rd();
for(int i=0;i<n;++i)b[i][i]=1;
for(int i=1;i<=n+1;++i){
mul(b,a,n);
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)inc(w[i][j&k],b[j][k]);
fmt(w[i],l,1);
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)c[i][j]=w[n-j][i];
c[i][n]=w[n+1][i];
}
gauss(c,n);
for(r=n;r&&!f[r];--r);
for(int i=n+2;i<=m;++i)
for(int j=0;j<n;++j)
for(int k=1;k<=r;++k){
inc(w[i][j],(ll)f[k]*w[i-k][j]%mod);
}
for(int i=0;i<n;++i)
for(int j=1;j<=m;++j)dec(h[i][j],w[j][i]);
int len=1;for(;len<=m;len<<=1);
for(int i=0;i<n;++i){
h[i][0]=1;
inv(h[i],g[i],len);
cls(g[i],m+1,len);
}
int ans=0;
for(int i=1;i<=m;++i){
for(int j=0;j<n;++j)w[i][j]=g[j][i];
fmt(w[i],l,-1);
for(int j=0;j<n;++j)ans^=w[i][j];
}
cout<<ans<<endl;
return 0;
}