QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178956#5377. $N$ 门问题Lynkcat#0 1ms3824kbC++202.6kb2023-09-14 15:52:072024-07-04 01:59:40

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:59:40]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3824kb
  • [2023-09-14 15:52:07]
  • 提交

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>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
Runtime Error

Test #1:

score: 5
Accepted
time: 0ms
memory: 3824kb

input:

1
2 3

output:

0.500000

result:

ok single line: '0.500000'

Test #2:

score: 5
Accepted
time: 1ms
memory: 3772kb

input:

1
3 5

output:

0.666667

result:

ok single line: '0.666667'

Test #3:

score: 5
Accepted
time: 1ms
memory: 3824kb

input:

1
4 5

output:

0.625000

result:

ok single line: '0.625000'

Test #4:

score: 0
Runtime Error

input:

1
0 4

output:

-nan

result:


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: 3768kb

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%