本文主要是介绍HDU 5159 Card 一次中出现两个也叫一次，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - 5159
set暴力超时：
int ans = 0,si = 0;
int x, b;
void dfs(set<int>cur, int t)
{if (t == 0){for (auto x : cur)ans += x;si++;return;}for (int i = 1; i <= x; i++){auto s = cur;s.insert(i);dfs(s, t - 1);}
}void solve(int c)
{ans = si = 0;cin >> x >> b;for (int i = 1; i <= x; i++){set<int>s;s.insert(i);dfs(s, b - 1);}cout << "Case #" << c << ": ";printf("%.3llf\n", ans*1.0 / si);
}signed main()
{//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;for (int i = 1; i <= t; i++){solve(i);}return 0;
}思路：
//其实dfs已经转化了一部分问题了
//我们求总和就好了
//
// 每个数*出现*就贡献一次，然而同时出现两次也只贡献一次，正着算重复情况难处理
// 不如-> 总次数减去未出现的次数就是出现次数
//（一次中出现两个也叫一次 ，比如1 ： 1 2 3 和 1 1 1 各是1次）
// 每个位置有x个选择，b个位置：
// x^b
// 一个数每个位置都不出现 (x-1)^b
// (x^b - (x-1)^b)*(1+2+...+x) / x^b
公式化简，直接求幂会溢出
//(1-((x-1)/x)^b) * (1+x)*x/2
代码：
double ksm(double x, int y) {if (x == 1) return 1.0;double res = 1, base = x;while (y) {if (y & 1) res = (res * base);base = (base * base) ;y >>= 1;}return res;
}int x, b;
void solve(int c)
{cin >> x >> b;cout << "Case #" << c << ": ";double tmp = (x - 1)*1.0 / x;double ans = (1 - ksm(tmp, b)) * (1 + x) * x / 2;printf("%.3llf\n", ans);
}signed main()
{//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;for (int i = 1; i <= t; i++){solve(i);}return 0;
}这篇关于HDU 5159 Card 一次中出现两个也叫一次的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
