0%

uoj#272 题解 - 【清华集训2016】石家庄的工人阶级队伍比较坚强

题目链接

题意非常的恶心。先理一下。考虑两个人 $x,y$,他们的剪刀石头布结果是 $b((x\oplus y)_{\text{cnt2}},(x\oplus y)_{\text{cnt1}})$,其中 $\oplus$ 表示三进制不进位加法,可以类比异或;而 $_{\text{cnt2}}$ 表示 $2$ 的个数。那么设这个东西为 $B_{y,x}$,要求的就是

我们发现

这个性质非常的优秀!我们有

于是这个矩阵就只有第一列是有意义的。考虑矩阵乘法:

于是就是“迫真子集卷积”。子集卷积是在每一维上做长度为 2 的 $\text{DFT}$,那么在每一维上做长度为 3 的 $\text{DFT}$ 即可。

需要 $\sqrt {-3}$,暴力扩域即可。还需要 $3^{-1}$,题目保证了直接 $(2p+1)/3$ 即可。

有个卡常小技巧:$\text{FWWT}(B)$ 结果的本质不同的值很少(不知道为什么QAQ),可以省掉极多的快速幂。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

int M,K,N=1,p;
int inline check(int x){return x>=p?x-p:x;}
struct Z{
int a,b;
Z(int a0=0,int b0=0):a(a0),b(b0){}
Z operator +(const Z v)const{return Z(check(a+v.a),check(b+v.b));}
Z operator -(const Z v)const{return Z(check(a-v.a+p),check(b-v.b+p));}
Z operator *(const Z v)const{return Z(check(1LL*a*v.a%p-3LL*b%p*v.b%p+p),check(1LL*a*v.b%p+1LL*b*v.a%p));}
bool operator <(const Z v)const{return a<v.a||(a==v.a&&b<v.b);}
}w,w2,F[531441],G[531441];
int inv2,inv3;
int B[13][13];

Z qpow(Z a,int k){Z ans=1;while(k){if(k&1) ans=ans*a;a=a*a;k>>=1;}return ans;}
int qpow(int a,int k){int ans=1;while(k){if(k&1) ans=1LL*ans*a%p;a=1LL*a*a%p;k>>=1;}return ans;}
void FWWT(Z d[],bool flg){
for(int n=1;n<N;n*=3)
for(Z *j=d;j<d+N;j+=n*3)
for(Z *k0=j,*k1=j+n,*k2=j+n+n;k0<j+n;k0++,k1++,k2++){
Z D0=*k0+*k1+*k2,
D1=*k0+*k1*w+*k2*w2,
D2=*k0+*k1*w2+*k2*w;
if(flg) swap(D1,D2);
*k0=D0,*k1=D1,*k2=D2;
}
}

map<Z,Z> WTF;

int main(){
scanf("%d%d%d",&M,&K,&p);inv2=(p+1)/2,inv3=(2*p+1)/3;
w=Z(p-inv2,inv2);w2=Z(p-inv2,p-inv2);
for(int i=1;i<=M;i++) N*=3;
for(int i=0;i<N;i++) scanf("%d",&F[i].a);
for(int i=0;i<=M;i++)
for(int j=0;i+j<=M;j++) scanf("%d",&B[i][j]);
for(int i=0;i<N;i++){
int i1=i,cnt1=0,cnt2=0;
while(i1) cnt1+=(i1%3==1),cnt2+=(i1%3==2),i1/=3;
G[i]=Z(B[cnt1][cnt2]);
}
FWWT(G,0);FWWT(F,0);
for(int i=0;i<N;i++)
if(!WTF.count(G[i])) F[i]=F[i]*(WTF[G[i]]=qpow(G[i],K));
else F[i]=F[i]*WTF[G[i]];
FWWT(F,1);
inv3=qpow(inv3,M);
for(int i=0;i<N;i++) printf("%d\n",1LL*F[i].a*inv3%p);
}

彩蛋