QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746856#9752. 覆盖一个环NananiAC ✓97ms21488kbC++201.2kb2024-11-14 15:43:502024-11-14 15:43:51

Judging History

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

  • [2024-11-14 15:43:51]
  • 评测
  • 测评结果:AC
  • 用时:97ms
  • 内存:21488kb
  • [2024-11-14 15:43:50]
  • 提交

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);
    }
    v[now] = 1;
    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

这程序好像有点Bug,我给组数据试试?

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

input:

20 20

output:

1.0000000000

result:

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

Test #3:

score: 0
Accepted
time: 2ms
memory: 10060kb

input:

20 19

output:

2.0526315789

result:

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

Test #4:

score: 0
Accepted
time: 97ms
memory: 21488kb

input:

20 1

output:

71.9547931429

result:

ok found '71.954793143', expected '71.954793143', error '0.000000000'

Test #5:

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

input:

18 17

output:

2.0588235294

result:

ok found '2.058823529', expected '2.058823529', error '0.000000000'

Test #6:

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

input:

18 16

output:

2.1911764706

result:

ok found '2.191176471', expected '2.191176471', error '0.000000000'

Test #7:

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

input:

18 15

output:

2.3500000000

result:

ok found '2.350000000', expected '2.350000000', error '0.000000000'

Test #8:

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

input:

18 14

output:

2.5428571429

result:

ok found '2.542857143', expected '2.542857143', error '0.000000000'

Test #9:

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

input:

18 13

output:

2.7802197802

result:

ok found '2.780219780', expected '2.780219780', error '0.000000000'

Test #10:

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

input:

18 2

output:

30.0428145384

result:

ok found '30.042814538', expected '30.042814538', error '0.000000000'

Test #11:

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

input:

1 1

output:

1.0000000000

result:

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

Extra Test:

score: 0
Extra Test Passed