QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746853#9752. 覆盖一个环NananiTL 1ms9980kbC++201.2kb2024-11-14 15:43:242024-11-14 15:43:25

Judging History

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

  • [2024-11-14 15:43:25]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9980kb
  • [2024-11-14 15:43:24]
  • 提交

answer

//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 2e6 + 10;
const int inf = 1e18;
typedef array<int, 3> a3; 
typedef long long ll;

int n, m, v[N], qaq[N];
double f[N];

double dfs(int now) {
    if(now == ((1 << n) - 1)) return 0;
    if(v[now]) return f[now];
    double &res = f[now];
    int cnt = 0;
    double sum = 0;
    F(i, 0, n - 1) {
        int nxt = now | qaq[i];
        if(nxt == now) {
            cnt ++;
            continue;
        }
        sum += (1.0 / n) * dfs(nxt);
    }
    res = (sum + 1) * (1.0 * n / (n - cnt));
    return res;
}

void sol() {
    cin >> n >> m;
    F(i, 0, n - 1) {
        F(j, 0, m - 1) {
            int u = (i + j) % n;
            qaq[i] |= (1 << u);
        }
    }
    cout << fixed << setprecision(10);
    cout << dfs(0) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    F(i, 1, t) sol();
    return 0;
}
//sldl

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

3 2

output:

2.5000000000

result:

ok found '2.500000000', expected '2.500000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

20 20

output:

1.0000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 9980kb

input:

20 19

output:

2.0526315789

result:

ok found '2.052631579', expected '2.052631579', error '0.000000000'

Test #4:

score: -100
Time Limit Exceeded

input:

20 1

output:


result: