自动搬运

查看原文

来自洛谷，原作者为

	Iang_ 若有南墙，撞破便是

搬运于2025-08-24 22:17:18，当前版本为作者最后更新于2021-02-25 22:53:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙题

注意到一个正方体的种类只跟其八个角上的字符相关，所以考虑枚举每个角上填的字符，把八个角分成两层，每层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]$。

答案即为： $\sum f[i][x][y]*f[i][x][z]*f[i][y][z]*f[x][y][z]$（一层有四个点，f数组限定了另一层的填法）。

ps：将每个单词翻转加入字符串去重可解决。

#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;
}