P9249
Larunatrecy
·
·
题解
一个暴力。
对于 S\in [0,n)，求出旅行的预约值的按位与为 S 的超集的方案数，然后做高维差分就能得到答案。
这样做的好处是，如果我们枚举 y，那么所有所有旅行的起点和终点都只需要满足是 S 的超集即可。
设 f_{i,x} 为当前走了 i 步，位于 x 的方案数，转移分为两种：
f_{i,x}\times A_{x,y}\to f_{i+1,y}
因为旅行至少走一步，所以我们不妨钦定走一步，枚举新旅行的第二个节点。
同样的理由，初始化也应当钦定走一步。
最后的答案就是 $\sum\limits_{x\&S=x}f_{m,x}$。
把转移写成矩阵 $F$，同时设行向量 $P$ 为 $f$ 的初值，列向量 $Q$ 为求答案的系数数组。
那么恰好经过 $i$ 条边的方案数即为 $PF^{i-1}Q$ ，$i-1$ 是因为初始化先走了一步。
取 $B=\sqrt m$，预处理出 $PF^{k},k\in [0,B)$ 以及 $F^{kB}Q$，因为都是矩阵乘向量，单次复杂度 $O(n^2) $。
总复杂度 $O(n(n^2\sqrt m+n^3\log m+nm))$，能过。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 64;
const int M = 20005;
int n,m;
inline int myplus(int a,int b){return (a+b>=mod?a+b-mod:a+b);}
struct vec
{
int mt[N];
vec(){memset(mt,0,sizeof(mt));}
int &operator [](int x){return mt[x];}
}Ma[150],Mb[150];
int operator *(vec A,vec B)
{
int res=0;
for(int k=0;k<n;k++)
res=myplus(res,1ll*A[k]*B[k]%mod);
return res;
}
struct mat
{
int mt[N][N];
mat(){memset(mt,0,sizeof(mt));}
inline int* operator [](int x){return mt[x];}
}G;
mat operator *(mat A,mat B)
{
mat C;
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
C[i][j]=myplus(C[i][j],1ll*A[i][k]*B[k][j]%mod);
return C;
}
vec operator *(vec A,mat B)
{
vec C;
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)
C[i]=myplus(C[i],1ll*A[k]*B[k][i]%mod);
return C;
}
vec operator *(mat A,vec B)
{
vec C;
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)
C[i]=myplus(C[i],1ll*A[i][k]*B[k]%mod);
return C;
}
mat Pow(mat a,int b)
{
mat res;
for(int i=0;i<n;i++)res[i][i]=1;
while(b)
{
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int A[N][N];
int f[M][N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&A[i][j]);
int B=sqrt(m)+1;
int K=log2(n);
for(int S=0;S<n;S++)
{
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=0;j<n;j++)
{
G[j][i]=A[j][i];
if((j|S)==j)sum=myplus(sum,A[j][i]);
}
Ma[0][i]=sum;
Mb[0][i]=((i|S)==i);
for(int j=0;j<n;j++)
if((j|S)==j)G[j][i]=myplus(G[j][i],sum);
}
for(int i=1;i<=B;i++)Ma[i]=Ma[i-1]*G;
G=Pow(G,B);
for(int i=1;i<=B;i++)Mb[i]=G*Mb[i-1];
for(int i=0;i<m;i++)f[i+1][S]=Ma[i%B]*Mb[i/B];
}
int ans=0;
for(int E=1;E<=m;E++)
{
for(int i=0;i<K;i++)
for(int j=0;j<n;j++)
if((j>>i)%2==0)f[E][j]=myplus(f[E][j],mod-f[E][j^(1<<i)]);
for(int i=0;i<n;i++)ans^=f[E][i];
}
cout<<ans;
return 0;
}
```