QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178961 | #5377. $N$ 门问题 | Lynkcat# | 0 | 1ms | 3836kb | C++20 | 2.6kb | 2023-09-14 15:53:35 | 2024-07-04 01:59:42 |
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
// #define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 1000005
using namespace std;
ll x, y, d; int n;
void exgcd(ll &x, ll &y, ll a, ll b) {
if(!b) d = a, x = 1, y = 0;
else exgcd(y, x, b, a % b), y -= a / b * x;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll a, b, A, B;
map<vector<pa>,double>dp;
double dfs(vector<pa> g)
{
if (g.size()==2) return g.back().se;
if (dp.count(g)) return dp[g];
int len=g.size()-1;
double res=inf;
for (int i=0;i+1<g.size();i++)
if (g[i].se!=1)
{
int nw=g[i].fi;
vector<pa> nxt;
for (int j=0;j+1<g.size();j++)
{
if (j!=i)
nxt.push_back(mp(nw/(g.size()-2)+g[j].fi,g[j].se));
}
nxt.push_back(g.back());
sort(nxt.begin(),nxt.end());
int tot=0;
double sm=0;
for (int k=0;k<nxt.size();k++)
{
if (nxt[k].fi==nxt.back().fi) tot++;
}
sm+=dfs(nxt);
if (tot!=1)
{
swap(nxt.back(),nxt[nxt.size()-2]);
sm+=dfs(nxt)*(tot-1);
}
sm/=tot;
res=min(res,sm);
}
return dp[g]=res;
}
void merge()
{
exgcd(x, y, a, A);
ll c = B - b;
if(c % d)
{
cout<<"error"<<endl;
exit(0);
}
x = x * c / d % (A / d);
if(x < 0) x += A / d;
ll mod = lcm(a, A);
b = (a * x + b) % mod; if(b < 0) b += mod;
a = mod;
}
void BellaKira()
{
int t;
cin>>t;
for(int i = 1 ; i <= t ; ++ i)
{
long long _A, _B;
cin>>_B>>_A;
A = _A, B = _B;
if(i > 1) merge();
else a = A, b = B;
}
int n=b%a;
if (n==0) n+=a;
if (n>10)
{
cout<<0.000000<<'\n';
return;
}
// cout<<"!"<<n<<endl;
int x=1;
for (int i=1;i<=n;i++) x=x*i;
vector<pa> g;
for (int i=1;i<n;i++)
g.push_back(mp(x,0));
g.push_back(mp(x,1));
double ans=dfs(g);
swap(g.back(),g[g.size()-2]);
ans+=(n-1)*dfs(g);
cout<<fixed<<setprecision(6)<<ans/n<<endl;
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3824kb
input:
1 2 3
output:
0.500000
result:
ok single line: '0.500000'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3728kb
input:
1 3 5
output:
0.666667
result:
ok single line: '0.666667'
Test #3:
score: 5
Accepted
time: 1ms
memory: 3836kb
input:
1 4 5
output:
0.625000
result:
ok single line: '0.625000'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3720kb
input:
1 0 4
output:
0.625000
result:
wrong answer 1st lines differ - expected: 'error', found: '0.625000'
Subtask #2:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
8 1 160005726539569 1 233 0 1 1 2947295521 1 686719856393 1 54289 1 12649337 1 37281334283719577
output:
1000000000000000000.000000
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 0ms
memory: 3720kb
input:
15 15 17 2 3 5 31 4 5 12 29 38 41 3 11 44 47 16 23 11 19 6 13 3 37 1 2 21 43 5 7
output:
0
result:
wrong answer 1st lines differ - expected: '0.000000', found: '0'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%