（noip 模拟 Fseq）<转化为多重集合的排列问题>

Problem

【问题描述】 一个长度为N+M的数列，里面有N个+1,M个-1 如果一个这样的数列被称作F序列(Fadeness) ， 当且仅当它的任意前缀和均非负。 for example : 1,-1,1,1,-1 is a Fadeness 1,-1,-1,1,1 is not because S(3) <0 求一个数列是Fadensee的概率。

【输入格式】 第一行，Test , 表示测试数据的组数。 每个数据 有两个数N,M

【输出格式】 对于每组数据,输出一个实数（保留到小数点后6位）

【样例输入1】 fseq.in 3 1 0 0 1 1 1 【样例输出1】 fseq.out 1.000000 0.000000 0.500000 【数据范围】 30%的数据：(Test<=10),(0<=N,M<=1000). 100%的数据：( Test<=9008 )，( 0<=N,M<=20000 ).

Solution

算法：组合数学题 可以将原问题转化一下，看成是在一个二维平面上行走，+1看成移动(1,0) -1看成移动(0,1)，那么到达(N,M)点且路线又不走到y=x这条直线上方的路线总数就是 答案，这个组合问题很经典，方案数为

C(M,M+N)−C(M−1,M+N) 所以 可以知道答案就是 1−M/(N+1)

Code

// #pragma GCC optimize(3) #include "bits/stdc++.h" using namespace std; #ifdef __attribute__ #define fast __attribute__((optimize(3), target("no-ieee-fp,arch=corei7"))) #define inline fast inline #else #define fast #endif namespace io { // #define USE_FREAD_IO #ifdef USE_FREAD_IO #define BUF_SIZE 5000010 char buf[BUF_SIZE]; int cur = BUF_SIZE; FILE *in = stdin; inline char gnc() { if (cur == BUF_SIZE) { fread(buf, BUF_SIZE, 1, in); cur = 0; } return buf[cur++]; } #else inline char gnc() { return (char)getchar(); } #endif template<typename T> inline void gi(T &dx) { dx = 0; int yc = gnc(); bool nega = false; while (yc < '0' || yc > '9') { nega = (yc == '-' ? true : nega); yc = gnc(); } while (yc >= '0' && yc <= '9') { dx = (T)(dx * 10 + yc - '0'); yc = gnc(); } if (nega) { dx = -dx; } } void gc(char &a) { do a = gnc(); while (!isgraph(a)); } void gss(char *c) { *c = gnc(); while (!isgraph(*c)) *c = gnc(); while (isgraph(*c)) *++c = gnc(); *c = 0; } #if __cplusplus >= 201103l || (defined(_MSVC_LANG) && _MSVC_LANG >= 201103l) template<typename T, typename ...Args> inline void gi(T &a, Args &...args) { gi(a); gi(args...); } #else template<typename t1, typename t2> inline void gi(t1 &a, t2 &b) { gi(a); gi(b); } template<typename t1, typename t2, typename t3> inline void gi(t1 &a, t2 &b, t3 &c) { gi(a); gi(b); gi(c); } template<typename t1, typename t2, typename t3, typename t4> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d) { gi(a); gi(b); gi(c); gi(d); } template<typename t1, typename t2, typename t3, typename t4, typename t5> inline void gi(t1 &a, t2 &b, t3 &c, t4 &d, t5 &e) { gi(a); gi(b); gi(c); gi(d); gi(e); } #endif } using namespace io; typedef long long ll; double calc(int n, int m) { if (m > n) return 0; return double(n - m + 1) / (n + 1); } int main() { freopen("fseq.in","r",stdin); freopen("fseq.out","w",stdout); int T; gi(T); while (T--) { int n, m; gi(n, m); printf("%.6lf\n", calc(n, m)); } return 0; }