| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 853224 | 2023-09-23T16:39:05 Z | alexdd | Fishing Game (RMI19_fishing) | C++17 | 489 ms | 218128 KB |
#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
*/
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 6488 KB | Output isn't correct |
| 2 | Incorrect | 1 ms | 8540 KB | Output isn't correct |
| 3 | Incorrect | 3 ms | 22876 KB | Output isn't correct |
| 4 | Incorrect | 8 ms | 45660 KB | Output isn't correct |
| 5 | Incorrect | 80 ms | 111196 KB | Output isn't correct |
| 6 | Incorrect | 127 ms | 132180 KB | Output isn't correct |
| 7 | Incorrect | 208 ms | 154520 KB | Output isn't correct |
| 8 | Incorrect | 273 ms | 177096 KB | Output isn't correct |
| 9 | Incorrect | 376 ms | 199668 KB | Output isn't correct |
| 10 | Incorrect | 489 ms | 218128 KB | Output isn't correct |