Submission #853247

#	Time	Username	Problem	Language	Result	Execution time	Memory
853247		alexdd	Fishing Game (RMI19_fishing)	C++17	100 / 100	486 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];
                    int initab=ab,initbc=bc,initca=ca;
                    for(int a=0;a<2;a++)
                    {
                        if(((a==0 && ab==0 && ab+ca>0) || (a==1 && ca==0)))
                            continue;
                        bool difa=0;
                        if(ab+ca>0)
                            difa=1;
                        if(a==0)///scoatem ab
                        {
                            if(difa)
                            {
                                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 && bc+ab>0) || (b==1 && ab==0))
                                continue;
                            bool difb=0;
                            if(bc+ab>0)
                                difb=1;
                            if(b==0)///scoatem bc
                            {
                                if(difa)
                                {
                                    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 && ca+bc>0) || (c==1 && bc==0))
                                    continue;
                                bool difc=0;
                                if(ca+bc>0)
                                    difc=1;
                                if(c==0)///scoatem ca
                                {
                                    if(difc)
                                    {
                                        prod*=ca;
                                        prod%=MOD;
                                        ca--;
                                    }
                                }
                                else///scoatem bc
                                {
                                    prod*=bc;
                                    prod%=MOD;
                                    bc--;
                                    ab++;
                                }
                                if(ab!=initab || bc!=initbc || ca!=initca)
                                {
                                    dp[ab][bc][ca]+=prod;
                                    dp[ab][bc][ca]%=MOD;
                                }
                                if(c==0)///scoatem ca
                                {
                                    if(difc)
                                    {
                                        ca++;
                                        prod*=inv[ca];
                                        prod%=MOD;
                                    }
                                }
                                else///scoatem bc
                                {
                                    bc++;
                                    ab--;
                                    prod*=inv[bc];
                                    prod%=MOD;
                                }
                            }
                            if(b==0)///scoatem bc
                            {
                                if(difb)
                                {
                                    bc++;
                                    prod*=inv[bc];
                                    prod%=MOD;
                                }
                            }
                            else///scoatem ab
                            {
                                ab++;
                                ca--;
                                prod*=inv[ab];
                                prod%=MOD;
                            }
                        }
                        if(a==0)///scoatem ab
                        {
                            if(difa)
                            {
                                ab++;
                                prod*=inv[ab];
                                prod%=MOD;
                            }
                        }
                        else///scoatem ca
                        {
                            ca++;
                            bc--;
                            prod*=inv[ca];
                            prod%=MOD;
                        }
                    }
                }
            }
        }
        cout<<dp[0][0][0]<<"\n";
    }
    return 0;
}

• Subtask 1: 100 / 100