炫酷回文

本文主要是介绍炫酷回文，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

小希拿到了一个很长的两行的字符矩阵，她想知道里面有多少个子矩阵的字符取出后通过某种排列可以构成一个回文串。

该字符矩阵内仅含有数字0-9。

【输入描述】

第一行输入一个整数N，表示字符矩阵的长度为N。
随后两行，每行N个字符，表示字符矩阵。

1≤N≤1000000

【输出描述】

输出一个整数，表示有多少个子矩阵的字符取出后通过某种排列可以构成一个回文串。

【样例】

示例1

输入
2
00
00
输出
9

示例1

输入
10
0313512342
1231345123
输出
28

思路：

如果一个子矩阵的字符串可以单独组成回文串，那么其中奇数个的字符最多只有一个，对每一位数字进行状压，第 i 位为 1 时表示 i 出现的次数为奇数次，从左向右维护矩形前缀异或和，那么当子矩阵异或和的二进制只有 1 或 0 个奇数位时，能单独组成回文串

【源代码】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define INF 0x3f3f3f3f
#define N 1000001
#define LL long long
const int MOD=998244353;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
using namespace std;
int n;
char a[N],b[N];//第一、二行数字
LL dpA[N],dpB[N],dp[N];//第一、二行与整体的前缀异或和
int sumA[N],sumB[N],sum[N];//第一、二行与整体的子矩阵回文数
int main(){scanf("%d",&n);scanf("%s",a+1);//第一行的每一位scanf("%s",b+1);//第二行的每一位LL res=0;dpA[0]=1;dpB[0]=1;dp[0]=1;for (int i = 1; i <= n; i++){//字符型转为整型int numA=a[i]-'0';int numB=b[i]-'0';//前缀异或和sumA[i]=sumA[i-1]^(1<<(numA));sumB[i]=sumB[i-1]^(1<<(numB));sum[i]=sum[i-1]^(1<<(numA))^(1<<(numB));//统计子矩阵回文数res += dp[sum[i]] + dpA[sumA[i]] + dpB[sumB[i]];for(int j=0;j<=9;j++)res+=dpA[sumA[i]^(1<<j)] + dpB[sumB[i]^(1<<j)] + dp[sum[i]^(1<<j)];dpA[sumA[i]]++;dpB[sumB[i]]++;dp[sum[i]]++;}printf("%lld\n",res);
}

 

这篇关于炫酷回文的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---