P7930 [COCI 2021/2022 #1] Set
题目背景
在知名游戏 SET 中，存在着一些数字、形状、颜色等不同的卡片，玩家的目标是确定一个存在的 triplet of cards（即卡片的三元组，也就是三张卡片构成的组合），使其符合特定的要求。Marin 和 Josip 很快就对这个游戏感到无趣，并对其进行了加强。
题目描述
在本题中，定义每张卡片代表着一个仅由 $ 1, 2, 3 $ 构成的长度为 $ k $ 的序列，共有 $ n $ 张卡片，卡片之间是无序的，保证卡片两两不同。
定义一个 SET 表示，当且仅当一个无序的 triplet of cards 其中的三个序列的每一位均相同或各不相同，用原文中的话就是 same 或 pairwise different，更严谨地表示，我们令这三个序列为 $ S_i, S_j, S_k $，则一定满足如下条件：
- $ i \lt j \lt k $
- $ \forall x \in \left[1, k\right] $，满足 $ S_i(x) = S_j(x) = S_k(x) $ 或 $ S_i(x) \neq S_j(x) \neq S_k(x) $
例如 $ (1123, 1322, 1221) $ 便满足 $ 1, 3 $ 位均相同，$ 2,4 $ 位各不相同。
给你这些序列，求可以组成多少种本质不同的 SET。
输入格式
第一行为两个整数正整数 $ n, k $。
接下来 $ n $ 行中每一行包含一个仅由 $ 1, 2, 3 $ 构成的长度为 $ k $ 的序列，代表着一张卡片。
保证每张卡片上的序列不同。
输出格式
仅一行一个整数，表示可以组成的本质不同的 SET 的数量。
输入输出样例 #1
输入 #1
3 4 1123 1322 1221输出 #1
1输入输出样例 #2
输入 #2
2 2 11 22输出 #2
0输入输出样例 #3
输入 #3
5 3 111 222 333 123 132输出 #3
2说明/提示
【样例解释 #3】
可以组成的两个 SET 分别为 $ (S_1, S_2, S_3) $ 和 $ (S_1, S_4, S_5) $。
【数据范围】
对于全部数据，1 ≤ k ≤ 12 1\le k\le 121≤k≤12，1 ≤ n ≤ 3 k 1\le n\le 3^k1≤n≤3k，S i S_iSi互不相同，1 ≤ S i ( x ) ≤ 3 1\le S_i(x) \le 31≤Si(x)≤3。
| Subtask | 特殊限制 | 分数 |
|---|---|---|
| 1 11 | k ≤ 5 k\le 5k≤5 | 10 1010 |
| 2 22 | k ≤ 7 k\le 7k≤7 | 30 3030 |
| 3 33 | 无特殊限制 | 70 7070 |
说明
本题总分110 110110分。
本题译自 Croatian Open Competition in Informatics 2021/2022 Contest #1 T4 Set。
思路
FWT即可。
代码见下
#include<bits/stdc++.h>usingnamespacestd;longlongn,k,uu=0,d[4000006],sl=1,sr=0;charch;constdoublepi=acos(-1.0);structone{doublex,y;}a[4000006],b[4000006];oneoperator+(one a1,one b1){returnone{a1.x+b1.x,a1.y+b1.y};}oneoperator-(one a1,one b1){returnone{a1.x-b1.x,a1.y-b1.y};}oneoperator*(one a1,one b1){returnone{a1.x*b1.x-a1.y*b1.y,a1.x*b1.y+a1.y*b1.x};}oneoperator/(one a1,doubleb1){returnone{a1.x/b1,a1.y/b1};}constone w=(one){-0.50,0.50*sqrt(3.00)};constone w2=(one){-0.50,-0.50*sqrt(3.00)};voidxor1(longlongn3,one*f,longlongx){//cout<<x<<endl;for(into=1;o<=n3-1;o*=3){for(inti=0;i<=n3-1;i+=o*3){for(intj=0;j<=o-1;j++){one t1=f[i+j],t2=f[i+j+o],t3=f[i+j+o*2];if(x==1){f[i+j]=t1+t2+t3;f[i+j+o]=t1+t2*w+t3*w2;f[i+j+o*2]=t1+t2*w2+t3*w;}else{f[i+j]=(t1+t2+t3)/3.00;f[i+j+o]=(t1+t2*w2+t3*w)/3.00;f[i+j+o*2]=(t1+t2*w+t3*w2)/3.00;}}}}return;}intmain(){cin>>n>>k;for(inti=0;i<=n-1;i++){uu=0;for(intj=1;j<=k;j++){cin>>ch;uu=uu*3+ch-'1';}d[uu]++;a[uu]=(one){1.00,0.00};//cout<<uu<<endl;}sl=pow(3,k);xor1(sl,a,1);for(inti=0;i<=sl-1;i++){//cout<<a[i].x<<" "<<a[i].y<<endl;a[i]=(a[i]*a[i]*a[i]);}xor1(sl,a,-1);//cout<<a[0].x<<endl;cout<<(longlong)((a[0].x+0.50-n)/6.00)<<endl;return0;}
