P6090 [CEOI2019] 立方填词
Iang_
·
·
题解
神仙题
注意到一个正方体的种类只跟其八个角上的字符相关，所以考虑枚举每个角上填的字符，把八个角分成两层，每层4个，记 G[len][j][k] 为长度为 len 第一个字符为j，最后一个字符为 k 的单词数。因为一个角相邻有三个角，记 f[x][y][z] 为这个角任意填k周围三个角上填的字符分别是 x,y,z 的方案数，f[x][y][z]=\sum_{k\in [0,127]} G[len][k][x]*G[len][k][y]*G[len][k][z]。
答案即为：
ps：将每个单词翻转加入字符串去重可解决。
```cpp
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int n,m,G[11][128][128],pos[128],f[128][128][128];
string s[200010];
char g[128];
bool vis[128];
long long ans;
int main()
{
freopen("cubeword.in","r",stdin);
freopen("cubeword.out","w",stdout);
scanf("%d",&n);
int x,y,z,i,j;
for(i=1;i<=n;i++) {
cin>>s[i];s[i+n]=s[i];
reverse(s[i+n].begin(),s[i+n].end());
for(j=0;j<s[i].size();j++) vis[s[i][j]]=1;
}
n*=2;
sort(s+1,s+n+1);
n=unique(s+1,s+n+1)-s-1;
for(int i=0;i<128;i++) if(vis[i]) g[++m]=i,pos[i]=m;
for(int i=1;i<=n;i++) G[s[i].size()][pos[s[i][0]]][pos[s[i][s[i].size()-1]]]++;
for(int len=3;len<=10;len++) {
// memset(f,0,sizeof(f));
for(x=1;x<=m;x++)
for(y=1;y<=m;y++)
for(z=1;z<=m;z++) {
f[x][y][z]=0;
for(i=1;i<=m;i++)
f[x][y][z]=(f[x][y][z]+1ll*G[len][i][x]*G[len][i][y]%mod*G[len][i][z]%mod)%mod;
}
for(i=1;i<=m;i++)
for(x=1;x<=m;x++)
for(y=1;y<=m;y++)
for(z=1;z<=m;z++)
ans=(ans+1ll*f[i][x][y]*f[i][x][z]%mod*f[i][y][z]%mod*f[x][y][z]%mod)%mod;
}
printf("%lld",ans);
return 0;
}
```