# [Title Description]

Xiaoxi gets a very long two line character matrix. She wants to know how many sub matrix characters are taken out to form a palindrome string through some arrangement.

The character matrix contains only digits 0-9.

# [insert description]

Enter an integer N in the first line to indicate that the length of the character matrix is N.
The next two lines, N characters in each line, represent the character matrix.

1≤N≤1000000

# [output description]

Output an integer to indicate how many characters of the submatrix can be taken out to form a palindrome string through some arrangement.

# [example]

Example 1

input
2
00
00
output
9

Example 1

input
10
0313512342
1231345123
output
28

Train of thought:

If the strings of a submatrix can form palindrome strings separately, there is at most one odd character among them, and each digit is pressed. If the i-th digit is 1, it means that the number of times I occurs is odd, and the rectangular prefix XOR sum is maintained from left to right. Then when the binary of the XOR sum of the submatrix has only 1 or 0 odd digits, it can form palindrome strings separately

# [source code]

```#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];//First and second lines of numbers
LL dpA[N],dpB[N],dp[N];//The prefix exclusive or sum of the first and second lines and the whole
int sumA[N],sumB[N],sum[N];//The first and second lines and the number of palindromes of the whole submatrix
int main(){

scanf("%d",&n);
scanf("%s",a+1);//Everyone in the first line
scanf("%s",b+1);//Everyone in the second line

LL res=0;
dpA[0]=1;
dpB[0]=1;
dp[0]=1;
for (int i = 1; i <= n; i++){
//Character to integer
int numA=a[i]-'0';
int numB=b[i]-'0';

//Prefix exclusive or and
sumA[i]=sumA[i-1]^(1<<(numA));
sumB[i]=sumB[i-1]^(1<<(numB));
sum[i]=sum[i-1]^(1<<(numA))^(1<<(numB));

//Statistical submatrix palindromes
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);
}```

Tags: Programming

Posted on Sun, 01 Dec 2019 14:27:13 -0800 by nublet