loj548 「LibreOJ β Round #7」某少女附中的体育课

时间:2024-05-24 16:34:50

这道题好神啊!!!

发现这题就是定义了一种新的卷积,然后做k+1次卷积。

这里我们就考虑构造一个变换T,使得$T(a) \cdot T(b) =T(a∘b)$,这里是让向量右乘这个转移矩阵。

于是我们可以得到

$$\sum_{j=0}^{m-1}{T_{j,i}  \sum{[k ∘ l =j] a_{k} b_{l}}  }   = (\sum_{j=0}^{m-1}{T_{j,i}a_{j}}) \cdot  (\sum_{j=0}^{m-1}{T_{j,i}b_{j}})$$

$$\sum{T_{k∘l,i}{a_{k}b_{l}}}= \sum{T_{k,i}T_{l,i}a_{k} b_{l}}$$

设x为T的某一列向量,这个变换满足的条件就是$x_{j}x_{k}=x_{j∘k}$

又因为循环律,设$c_{i}$为$i$的周期长度,我们发现$x_{i^{c_{i}}}=x_{i}^{c_{i}}=x_{i}$,所以$x_{i}=w_{c_{i}}^{k} or 0$。

之后我们发现合法的情况只有n种,考虑暴搜变换然后加上上面那个减枝就可以了。

然后我们就得到了我们要求的变换,然后就像fwt一样每一维依次进行变换就可以了。

正解依旧没有看懂,我的理解就是按照$x^{0}$分成若干个等价类,对于每个等价类内dft构造出一个其中若干个变换,然后在将每个小变换扩展全部,但是具体的怎么dft以及如何扩展的我还不是特别明白,所以先挖个大坑吧。其实我觉得这种需要构造变换的题暴搜都是可以碾压正解的,因为暴搜加减枝的复杂度真的很优秀。

最后,LCA太神啦!

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define mod 232792561
#define N 500500
#define M 25
using namespace std;
int rt=,n,m,all,f[N],tmp[N];
int A[M][M],a[M],cnt[M],tot,w[M][M],C[M][M],D[M][M];
long long K;
int qp(int a,int b){
int c=;
for(;b;b>>=,a=1ll*a*a%mod)
if(b&)c=1ll*c*a%mod;
return c;
}
void UPD(int &a,int b){
a=(a+b>=mod)?(a+b-mod):(a+b);
}
bool can(int x){
for(int i=;i<=x;i++)
for(int j=;j<=x;j++)
if(A[i][j]<=x&&1ll*a[i]*a[j]%mod!=a[A[i][j]])return ;
return ;
}
void dfs(int x){
if(tot==m)return ;
if(x==m){
bool flag=;
for(int i=;i<m;i++)if(a[i])
{flag=;break;}
if(!flag)return ;
for(int i=;i<m;i++)C[i][tot]=a[i];
tot++;
return ;
}
for(int i=;i<=cnt[x];i++){
a[x]=w[cnt[x]][i];
if(can(x))dfs(x+);
}
}
void getni(){
for(int i=;i<m;i++)D[i][i]=;
for(int k=;k<m;k++){
if(!C[k][k]){
for(int i=k+;i<m;i++)if(C[i][k]){
for(int j=;j<m;j++){
swap(C[k][j],C[i][j]);
swap(D[k][j],D[i][j]);
}
}
}
int inv=qp(C[k][k],mod-);
for(int i=;i<m;i++){
C[k][i]=1ll*C[k][i]*inv%mod;
D[k][i]=1ll*D[k][i]*inv%mod;
}
for(int i=;i<m;i++)if(i!=k&&C[i][k]){
int t=C[i][k];
for(int j=;j<m;j++){
UPD(C[i][j],mod-1ll*t*C[k][j]%mod);
UPD(D[i][j],mod-1ll*t*D[k][j]%mod);
}
}
}
}
void dft(int n,int *f,int C[M][M]){
if(n==)return ;
int l=n/m;
for(int i=;i<m;i++)dft(l,f+i*l,C);
for(int i=;i<n;i++)tmp[i]=;
for(int i=;i<m;i++)
for(int j=;j<m;j++)
for(int k=;k<l;k++)
UPD(tmp[j*l+k],1ll*f[i*l+k]*C[i][j]%mod);
for(int i=;i<n;i++)
f[i]=tmp[i];
}
int main(){
//freopen("test.in","r",stdin);
for(int i=,now;i<=;i++){
w[i][]=;
now=qp(rt,(mod-)/i);
for(int j=;j<i;j++)
w[i][j]=1ll*w[i][j-]*now%mod;
}
scanf("%d%d%lld",&n,&m,&K);
K=(K+)%(mod-);
for(int i=;i<m;i++)
for(int j=;j<m;j++)
scanf("%d",&A[i][j]);
for(int i=;i<m;i++){
int now=i;
do{
cnt[i]++;
now=A[now][i];
}while(now!=i);
}
dfs();
all=qp(m,n);
for(int i=;i<all;i++)scanf("%d",&f[i]);
dft(all,f,C);
for(int i=;i<all;i++)f[i]=qp(f[i],K);
getni();
dft(all,f,D);
for(int i=;i<all;i++)printf("%d\n",f[i]);
return ;
}