Last active
December 18, 2015 20:48
-
-
Save lychees/5842537 to your computer and use it in GitHub Desktop.
UESTC 1888. Birthday Party
。。n 个点。每个点随机向某个自己以外的点连一条边。
。。。问存在一个 k 元环的概率。。
( n, k = 10^7 http://acm.uestc.edu.cn/problem.php?pid=1888&cid=219
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define LOCAL | |
/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/ | |
#include <algorithm> | |
#include <iostream> | |
#include <iomanip> | |
#include <sstream> | |
#include <cstring> | |
#include <cstdio> | |
#include <string> | |
#include <vector> | |
#include <bitset> | |
#include <queue> | |
#include <stack> | |
#include <cmath> | |
#include <ctime> | |
#include <list> | |
#include <set> | |
#include <map> | |
using namespace std; | |
#define REP(i, n) for (int i=0;i<int(n);++i) | |
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i) | |
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i) | |
#define REP_1(i, n) for (int i=1;i<=int(n);++i) | |
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i) | |
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i) | |
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i) | |
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i) | |
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i) | |
#define REP_N(i, n) for (i=0;i<int(n);++i) | |
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i) | |
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i) | |
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i) | |
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i) | |
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i) | |
#define REP_1_N(i, n) for (i=1;i<=int(n);++i) | |
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i) | |
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i) | |
#define REP_C_N(i, n) for (int n____=(i=0,int(n));i<n____;++i) | |
#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i<b____;++i) | |
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i>=a____;--i) | |
#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i<=n____;++i) | |
#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i<=b____;++i) | |
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i>=a____;--i) | |
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it) | |
#define DO(n) while(n--) | |
#define DO_C(n) int n_____ = n; while(n_____--) | |
#define ALL(A) A.begin(), A.end() | |
#define LLA(A) A.rbegin(), A.rend() | |
#define CPY(A, B) memcpy(A, B, sizeof(A)) | |
#define INS(A, P, B) A.insert(A.begin() + P, B) | |
#define ERS(A, P) A.erase(A.begin() + P) | |
#define BSC(A, X) find(ALL(A), X) // != A.end() | |
#define CTN(T, x) (T.find(x) != T.end()) | |
#define SZ(A) int(A.size()) | |
#define PB push_back | |
#define MP(A, B) make_pair(A, B) | |
#define Rush int T____; RD(T____); DO(T____) | |
#pragma comment(linker, "/STACK:36777216") | |
//#pragma GCC optimize ("O2") | |
#define Ruby system("ruby main.rb") | |
#define Haskell system("runghc main.hs") | |
#define Pascal system("fpc main.pas") | |
typedef long long LL; | |
typedef double DB; | |
typedef vector<int> VI; | |
template<class T> inline void RD(T &); | |
template<class T> inline void OT(const T &); | |
inline int RD(){ int x; RD(x); return x;} | |
template<class T> inline T& _RD(T &x){ RD(x); return x;} | |
inline void RC(char &c){scanf(" %c", &c);} | |
inline void RS(char *s){scanf("%s", s);} | |
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);} | |
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));} | |
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);} | |
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);} | |
template<class T> inline void CLR(T &A){A.clear();} | |
template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);} | |
/** Add - On **/ | |
const int MOD = 1000000007; | |
const int INF = 10009; | |
const DB EPS = 1e-2; | |
const DB OO = 1e15; | |
const DB PI = 3.14159265358979323846264; //M_PI; | |
// <<= ` 0. Daily Use ., | |
template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;} | |
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;} | |
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;} | |
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;} | |
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);} | |
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);} | |
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));} | |
template<class T> inline T max(T a, T b, T c, T d){return max(min(a, b), max(c, d));} | |
template<class T> inline T sqr(T a){return a*a;} | |
template<class T> inline T cub(T a){return a*a*a;} | |
int Ceil(int x, int y){return (x - 1) / y + 1;} | |
// <<= ` 1. Bitwise Operation ., | |
inline bool _1(int x, int i){return x & 1<<i;} | |
inline bool _1(LL x, int i){return x & 1LL<<i;} | |
inline LL _1(int i){return 1LL<<i;} | |
//inline int _1(int i){return 1<<i;} | |
inline LL _U(int i){return _1(i) - 1;}; | |
//inline int _U(int i){return _1(i) - 1;}; | |
inline int count_bits(int x){ | |
x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); | |
x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); | |
x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); | |
x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); | |
x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); | |
return x; | |
} | |
// <<= ' 0. I/O Accelerator interface ., | |
template<class T> inline void RD(T &x){ | |
//cin >> x; | |
scanf("%d", &x); | |
//char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0'; | |
} | |
template<class T> inline void OT(const T &p){ | |
printf("%.9f\n", p); | |
} | |
/* .................................................................................................................................. */ | |
const int N = 10000009; | |
DB f(){ | |
int n, k; RD(n, k); DB res = 0, cur = 1; int t = n; REP_1_C(i, n/k){ | |
cur /= i*k; DWN_1_C_N(t, t, t-k+1) cur *= (DB)t/(n-1); | |
if (i&1) res += cur; else res -= cur; | |
} | |
return res; | |
} | |
int main(){ | |
#ifndef ONLINE_JUDGE | |
//freopen("in.txt", "r", stdin); | |
//freopen("out.txt", "w", stdout); | |
#endif | |
Rush OT(f()); | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
//说不定你看不到站内信。。。。
include
include
using namespace std;
int main() {
int T;
scanf("%d", &T);
for(int cas=0; cas<T; ++cas) {
int n, k;
scanf("%d%d", &n, &k);
double p = 1.0;
double ans = 0.0;
for(int i=1; i*k<=n; ++i) {
for(int c=n-(i-1)k; c>n-ik; --c) {
p *= c;
p /= n-1;
}
p /= k;
p /= i;
if(i&1) ans += p;
else ans -= p;
}
printf("%.9lf\n", ans);
}
}