NC17621 pipe bead taking

Link: https://ac.nowcoder.com/acm/problem/17621 Source: niuke.com

Title Description

Pipe bead taking is a game that Xiao X likes very much. In this topic, we will consider a simple revision of the game. The game screen is shown in Figure 1:

At the beginning of the game, there are a certain number of small balls in the upper and lower pipes on the left (there are two types of dark colored balls and light colored balls), while the output pipe on the right is empty. For each operation, you can select a pipe from the left and push the rightmost ball in the pipe into the right output pipe.

For example, we first move a ball from the lower pipe to the output pipe, and we will get the situation shown in Figure 2.

 

Assuming that there are n balls in the upper pipe and M balls in the lower pipe, the whole game process requires n+m operations, that is, all the balls in the left pipe are moved into the output pipe. Finally, n+m balls form an output sequence from right to left in the output pipeline.

Little X, who loves mathematics, knows that he has C(n+m, n) different operation modes, and different operation modes may lead to the same output sequence. For example, for the game situation shown in Figure 3:

They use A for light colored balls and B for dark colored balls. If the operation of moving the ball on the right side of the upper pipe is U and the operation of moving the ball on the right side of the lower pipe is D, there are three different operation modes: uud, UDU and duu; Finally, the output sequences (from right to left) formed in the output pipeline are BAB, BBA and BBA respectively. It can be found that the latter two operation modes will get the same output sequence.

It is assumed that there are K different kinds of output sequences that may be generated in the end, and the generation mode of the i-th output sequence (i.e. the number of different operation modes) has ai. Smart little X already knows,

Therefore, small X wants to be calculated

Can you help him calculate this value? Since this value may be very large, you only need to output the modulus of 1024523 (i.e. the remainder divided by 1024523).

Note: in this paper, C(n+m,n) represents the combination number. The combination number C(a,b) is equivalent to the number of selection schemes for selecting B of a different items.

 

Enter Description:
The first line contains two integers n and m, which respectively represent the number of balls in the upper and lower pipes. The second line is an AB string with A length of N, indicating the type of ball from left to right in the upper pipe. Where A represents A light colored ball and B represents A dark colored ball. The third line is an AB string with A length of M, indicating the situation in the lower pipeline.
Output Description:
Contains only one line, which is the remainder divided by 1024523

Example 1

input

2 1
AB
B
output

5
remarks:
For 30% of the data, n, m ≤ 12; For 100% of the data, n, m ≤ 500.

Idea:

This question is quite ingenious. You should think of itThe physical meaning of: add an identical tube, ask two tubes to take the ball, and get the same number of solutions,

That is, the first tube takes BBA, and the second tube also takes the number of schemes of BBA.

Next is dp. Let dp[i] [j] [k] [l] be that I balls have been taken above tube 1, j balls have been taken below tube 1 and K balls have been taken above tube 2,

1 ball is taken under tube 2, and the arrangement results of tube 1 and tube 2 are the same.

Therefore, the transfer equation can be divided into four cases: a represents the ball above and b represents the ball below.

  1. When a [i] = = a [k], dp[i] [j] [k] [l]+=dp[i-1] [j] [k-1] [l];

  2. When a [i] = = B [l], dp[i] [j] [k] [l]+=dp[i-1] [j] [k] [l-1];

  3. When B [J] = = a [k], dp[i] [j] [k] [l]+=dp[i] [j-1] [k-1] [l];

  4. When B [J] = = B [l], dp[i] [j] [k] [l]+=dp[i] [j-1] [k] [l-1];

A space of 500 ^ 4 is bound to explode, but we know i+j=k+l because there are two identical tubes.

So l this one dimension can be omitted and replaced by i+j-k.

code:

#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<queue>
#include<bitset>
//#include<hash_map>
#define sd(x) scanf("%d",&x)
#define lsd(x) scanf("%lld",&x)
#define ms(x,y) memset(x,y,sizeof x)
#define fu(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
//using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int maxn=1e5+79;
const int mod=1024523;
const int INF=1e9+7;
const double pi=acos(-1);

int dp[506][506][506];
char a[506],b[506];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //std::ifstream fil;
    //fil.open("t.txt");
    //freopen("C.in","r",stdin);
    int n,m;
    sd(n);sd(m);
    scanf("%s",a+1);scanf("%s",b+1);
    dp[0][0][0]=1;
    fu(i,0,n)
    {
        fu(j,0,m)
        {
            fu(k,0,n)
            {
                int l=i+j-k;
                if(i&&k&&a[i]==a[k])
                dp[i][j][k]+=dp[i-1][j][k-1];
                if(i&&l&&a[i]==b[l])
                dp[i][j][k]+=dp[i-1][j][k];
                if(j&&k&&b[j]==a[k])
                dp[i][j][k]+=dp[i][j-1][k-1];
                if(j&&l&&b[j]==b[l])
                dp[i][j][k]+=dp[i][j-1][k];
                dp[i][j][k]%=mod;
            }
        }
    }
    printf("%lld\n",dp[n][m][n]);
    return 0;
}

 

Tags: dp

Posted by calmchess on Thu, 19 May 2022 08:05:52 +0300