QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#746853 | #9752. 覆盖一个环 | Nanani | TL | 1ms | 9980kb | C++20 | 1.2kb | 2024-11-14 15:43:24 | 2024-11-14 15:43:25 |
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);
}
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
詳細信息
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