Cool palindrome (basic algorithm training camp for 2019 ox winter vacation Day5-F)

[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