QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746856 | #9752. 覆盖一个环 | Nanani | AC ✓ | 97ms | 21488kb | C++20 | 1.2kb | 2024-11-14 15:43:50 | 2024-11-14 15:43:51 |
Judging History
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