# Cod sursa(job #2478553)

Utilizator Data 22 octombrie 2019 13:20:29 Iv 45 cpp-64 done Arhiva de probleme 2.98 kb
``````#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
const int MOD = 3210121;

{
a += b;
if (a >= MOD)
return a - MOD;
if (a < 0)
return a + MOD;
return a;
}

int mul(int a, int b)
{
return a * (ll) b % MOD;
}

const int N = 500 + 7;
int n, a[N];
int m, b[N];
string s, t;
int dp[N][N];
int ndp[N][N];
int p[5], val[5];

bool valid(int l, int x, int y)
{
return 1;
}

int main()
{
freopen ("iv.in", "r", stdin);
freopen ("iv.out", "w", stdout);

cin >> s >> t;
n = (int) s.size();
m = (int) t.size();

for (int i = 1; i <= n; i++)
a[i] = s[i - 1];
for (int i = 1; i <= m; i++)
b[i] = t[i - 1];

dp[0][0] = 1;
int len = (n + m) / 2;

for (int l = 0; l < len; l++)
{
for (int x = 0; x <= n; x++)
for (int y = 0; y <= m; y++)
if (dp[x][y])
{
p[1] = x + 1;
p[2] = n - y;
p[3] = (l - x) + 1;
p[4] = m - (l - y);
val[1] = a[p[1]];
val[2] = a[p[2]];
val[3] = b[p[3]];
val[4] = b[p[4]];
for (int f = 1; f <= 3; f += 2)
for (int s = 2; s <= 4; s += 2)
{
int vf = val[f], vs = val[s];
if (vf == vs)
{
if (f == 1 && s == 2 && p[1] == p[2]) continue;
if (f == 3 && s == 4 && p[3] == p[4]) continue;
ndp[x + (f == 1)][y + (s == 2)] = add(ndp[x + (f == 1)][y + (s == 2)], dp[x][y]);
}
}
}
for (int x = 0; x <= n; x++)
for (int y = 0; y <= m; y++)
{
dp[x][y] = ndp[x][y];
ndp[x][y] = 0;
}
}

int ans = 0;
for (int x = 0; x <= n; x++)
for (int y = 0; y <= m; y++)