Submission #853224

#	Time	Username	Problem	Language	Result	Execution time	Memory
853224		alexdd	Fishing Game (RMI19_fishing)	C++17	0 / 100	489 ms	218128 KiB

fishing

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int dp[305][305][305];
int cardA[205];
int cardB[205];
int cardC[205];
int inv[305];
int n;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<=300;i++)
        inv[i]=put(i,MOD-2);
    int t;
    cin>>n>>t;
    while(t--)
    {
        for(int i=1;i<=2*n;i++)
            cin>>cardA[i];
        for(int i=1;i<=2*n;i++)
            cin>>cardB[i];
        for(int i=1;i<=2*n;i++)
            cin>>cardC[i];
        int cntab=0,cntbc=0,cntca=0;
        for(int i=1;i<=2*n;i++)
        {
            for(int j=1;j<=2*n;j++)
            {
                if(cardA[i]==cardB[j])
                    cntab++;
                if(cardB[i]==cardC[j])
                    cntbc++;
                if(cardC[i]==cardA[j])
                    cntca++;
            }
        }
        for(int i=0;i<=3*n;i++)
            for(int j=0;j<=3*n;j++)
                for(int k=0;k<=3*n;k++)
                    dp[i][j][k]=0;
        dp[cntab][cntbc][cntca]=1;
        for(int tot=cntab+cntbc+cntca;tot>0;tot--)
        {
            for(int ab=0;ab<=tot;ab++)
            {
                for(int bc=0;bc+ab<=tot;bc++)
                {
                    int ca = tot-ab-bc;
                    if(dp[ab][bc][ca]==0)
                        continue;
                    int prod=dp[ab][bc][ca];
                    for(int a=0;a<2;a++)
                    {
                        if((a==0 && ab==0) || (a==1 && ca==0))
                            continue;
                        if(a==0)///scoatem ab
                        {
                            prod*=ab;
                            prod%=MOD;
                            ab--;
                        }
                        else///scoatem ca
                        {
                            prod*=ca;
                            prod%=MOD;
                            ca--;
                            bc++;
                        }
                        for(int b=0;b<2;b++)
                        {
                            if((b==0 && bc==0) || (b==1 && ab==0))
                                continue;
                            if(b==0)///scoatem bc
                            {
                                prod*=bc;
                                prod%=MOD;
                                bc--;
                            }
                            else///scoatem ab
                            {
                                prod*=ab;
                                prod%=MOD;
                                ab--;
                                ca++;
                            }
                            for(int c=0;c<2;c++)
                            {
                                if((c==0 && ca==0) || (c==1 && bc==0))
                                    continue;
                                if(c==0)///scoatem ca
                                {
                                    prod*=ca;
                                    prod%=MOD;
                                    ca--;
                                }
                                else///scoatem bc
                                {
                                    prod*=bc;
                                    prod%=MOD;
                                    bc--;
                                    ab++;
                                }
                                dp[ab][bc][ca]+=prod;
                                dp[ab][bc][ca]%=MOD;
                                if(c==0)///scoatem ca
                                {
                                    ca++;
                                    prod*=inv[ca];
                                    prod%=MOD;
                                }
                                else///scoatem bc
                                {
                                    bc++;
                                    ab--;
                                    prod*=inv[bc];
                                    prod%=MOD;
                                }
                            }
                            if(b==0)///scoatem bc
                            {
                                bc++;
                                prod*=inv[bc];
                                prod%=MOD;
                            }
                            else///scoatem ab
                            {
                                ab++;
                                ca--;
                                prod*=inv[ab];
                                prod%=MOD;
                            }
                        }
                        if(a==0)///scoatem ab
                        {
                            ab++;
                            prod*=inv[ab];
                            prod%=MOD;
                        }
                        else///scoatem ca
                        {
                            ca++;
                            bc--;
                            prod*=inv[ca];
                            prod%=MOD;
                        }
                    }
                }
            }
        }
        cout<<dp[0][0][0]<<"\n";
    }
    return 0;
}
/**

dp[ab][bc][ca] = numarul de moduri de a ajunge la o configuratie in care exista ab perechi care au un element in A si celalalt in B

dp[ab-1][bc-1][ca-1] += dp[ab][bc][ca] * ab * bc * ca    daca luam din A un ab, luam din B un bc, luam din C un ca

dp[ab-1-1][bc][ca-1+1] += dp[ab][bc][ca]    daca luam din A un ab, luam din B un ab, luam din C un ca


*/

• Subtask 1: 0 / 100