F - Yes or No

---

Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配點 : 2000 點

問題文

あなたは N+M 問のマルバツクイズが出題されるクイズゲームに參加します。

出題される問題のうち、N 問の正解がマル、M 問の正解がバツであることは事前に知らされていますが、問題は無作為な順序で出題されます。

あなたにはどの問題の正解も見當(dāng)がつきません。 問題には一問ずつ解答していき、解答するごとにその問題の正解をすぐに知ることができます。

ここで、あなたが問題に正解する回數(shù)の期待値を最大化する戦略をとったと仮定します。

この期待値を P?Q（既約分?jǐn)?shù)）とします。また、M=998244353 とします。このとき、0 以上 M?1 以下の整數(shù) R がただ一つ存在して P=Q×R mod M となることが証明でき、その値は P×Q^?1 mod M と等しくなります。ここで、Q^?1 は Q のモジュラ逆數(shù)です。R を求めてください。

制約

• 1≤N,M≤500,000
• N,M はともに整數(shù)である。

部分點

• N=M および 1≤N,M≤10⁵ を満たすデータセットに正解すると、1500 點が與えられる。

---

入力

入力は以下の形式で標(biāo)準(zhǔn)入力から與えられる。

N M

出力

P?Q を最適な戦略に従った場合の問題に正解する回數(shù)の期待値を表す既約分?jǐn)?shù)とする。P×Q^?1 mod 998244353 を出力せよ。

---

入力例 1

Copy 1 1

出力例 1

Copy 499122178

問題が二問あります。 一問目には無作為に答えてよく、正解する確率は 50% です。 そして、二問目の答えは一問目と異なることが分かっているため、二問目に正解する確率は 100% です。

以上から、正解數(shù)の期待値は 3 / 2 です。 したがって、P=3, Q=2, Q^?1=499122177 (mod 998244353), P×Q^?1=499122178 (mod 998244353) となります。

---

入力例 2

Copy 2 2

出力例 2

Copy 831870297

正解數(shù)の期待値は 17 / 6 です。

---

入力例 3

Copy 3 4

出力例 3

Copy 770074220

正解數(shù)の期待値は 169 / 35 です。

---

入力例 4

Copy 10 10

出力例 4

Copy 208827570

---

入力例 5

Copy 42 23

出力例 5

Copy 362936761

Score : 2000 points

Problem Statement

You are participating in a quiz with N+M questions and Yes/No answers.

It's known in advance that there are N questions with answer Yes and M questions with answer No, but the questions are given to you in random order.

You have no idea about correct answers to any of the questions. You answer questions one by one, and for each question you answer, you get to know the correct answer immediately after answering.

Suppose you follow a strategy maximizing the expected number of correct answers you give.

Let this expected number be P?Q, an irreducible fraction. Let M=998244353. It can be proven that a unique integer R between 0 and M?1 exists such that P=Q×R modulo M, and it is equal to P×Q^?1 modulo M, where Q^?1 is the modular inverse of Q. Find R.

Constraints

• 1≤N,M≤500,000
• Both N and M are integers.

Partial Score

• 1500 points will be awarded for passing the testset satisfying N=M and 1≤N,M≤10⁵.

---

Input

Input is given from Standard Input in the following format:

N M

Output

Let P?Q be the expected number of correct answers you give if you follow an optimal strategy, represented as an irreducible fraction. Print P×Q^?1 modulo 998244353.

---

Sample Input 1

Copy 1 1

Sample Output 1

Copy 499122178

There are two questions. You may answer randomly to the first question, and you'll succeed with 50% probability. Then, since you know the second answer is different from the first one, you'll succeed with 100% probability.

The expected number of your correct answers is 3 / 2. Thus, P=3, Q=2, Q^?1=499122177 (modulo 998244353), and P×Q^?1=499122178 (again, modulo 998244353).

---

Sample Input 2

Copy 2 2

Sample Output 2

Copy 831870297

The expected number of your correct answers is 17 / 6.

---

Sample Input 3

Copy 3 4

Sample Output 3

Copy 770074220

The expected number of your correct answers is 169 / 35.

---

Sample Input 4

Copy 10 10

Sample Output 4

Copy 208827570

---

Sample Input 5

Copy 42 23

Sample Output 5

Copy 362936761

?

設(shè)余x個Yes，y個No，則每次最優(yōu)的策略顯然是選擇多的那個。

整個過程可以用一個n*m的矩形及其上格點來表示（圖片參照官方題解）。（不妨設(shè)n>=m） 過程為從(n,m)走到(0,0)?

作直線y=x 易證在該直線右側(cè)區(qū)域（不含該直線）內(nèi)YES比NO多，即每一次回答YES。在y=x左側(cè)區(qū)域相反，在y=x上則為二者數(shù)量相等（不含（0，0））

首先可以證明一個結(jié)論：從（n,m）到（0，0）的任意路徑，不考慮其中經(jīng)過y=x的點，其余路徑選對的次數(shù)恰為n ?（任意坐標(biāo)（x,y）表示還有x個YES的問題，y個NO的問題）

證明如下：（以下的y=x左右亦不包含y=x）

設(shè)在y=x右側(cè)向左走a次（a>=n-m），則在y=x右側(cè)必向下走a-n+m次，在y=x左側(cè)必向下走n-a次。

而在y=x右側(cè)向左走表明選對，在y=x左側(cè)向下走表明選對。故總共n次。

這樣就將y=x以外的點的所有貢獻計算了出來 為n*C(n,m)/C(n,m)=n。

接下來只需要考慮y=x上的點。對于任意一點（a,a）其向左、向下走走對的可能性均為1/2 故對最終期望的貢獻為 (1/2)*C(n-i,n+m-2*i)*C(i,2*i)/C(n,m) ? （為該點期望乘以經(jīng)過該點的路徑數(shù)/總路徑數(shù)）

將兩種情況之和加起來即可。

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <vector> 5 #include <set> 6 #include <map> 7 #include <string> 8 #include <cstring> 9 #include <stack> 10 #include <queue> 11 #include <cmath> 12 #include <ctime> 13 #include<bitset> 14 #include <utility> 15 using namespace std; 16 #define rank rankk 17 #define mp make_pair 18 #define pb push_back 19 #define xo(a,b) ((b)&1?(a):0) 20 //#define LL ll 21 typedef unsigned long long ull; 22 typedef pair<int,int> pii; 23 typedef long long ll; 24 typedef pair<ll,int> pli; 25 const int INF=0x3f3f3f3f; 26 const ll INFF=0x3f3f3f3f3f3f3f3fll; 27 const int MAX=1e6+5; 28 const int MAX_N=MAX; 29 const ll MOD=998244353; 30 const long double pi=acos(-1.0); 31 //const double eps=0.00000001; 32 int gcd(int a,int b){return b?gcd(b,a%b):a;} 33 template<typename T>inline T abs(T a) {return a>0?a:-a;} 34 template<class T> inline 35 void read(T& num) { 36 bool start=false,neg=false; 37 char c; 38 num=0; 39 while((c=getchar())!=EOF) { 40 if(c=='-') start=neg=true; 41 else if(c>='0' && c<='9') { 42 start=true; 43 num=num*10+c-'0'; 44 } else if(start) break; 45 } 46 if(neg) num=-num; 47 } 48 inline ll powMM(ll a,ll b,ll M){ 49 ll ret=1; 50 a%=M; 51 // b%=M; 52 while (b){ 53 if (b&1) ret=ret*a%M; 54 b>>=1; 55 a=a*a%M; 56 } 57 return ret; 58 } 59 void open() 60 { 61 freopen("1009.in","r",stdin); 62 freopen("out.txt","w",stdout); 63 } 64 ll inv[MAX],fac[MAX]; 65 ll C(ll x,ll y) 66 { 67 return fac[x]*inv[y]%MOD*inv[x-y]%MOD; 68 } 69 int n,m;ll da=1e6; 70 ll an; 71 int main() 72 { 73 fac[0]=1;for(ll i=1;i<=da;i++)fac[i]=i*fac[i-1]%MOD; 74 inv[da]=powMM(fac[da],MOD-2,MOD);for(ll i=da;i>=1;i--)inv[i-1]=inv[i]*i%MOD; 75 scanf("%d%d",&n,&m);if(n<m)swap(n,m); 76 for(ll i=1;i<=m;i++) 77 an=(an+C(n+m-2*i,n-i)*C(2*i,i)%MOD)%MOD; 78 an=an*inv[2]%MOD*fac[n]%MOD*fac[m]%MOD*inv[n+m]%MOD; 79 printf("%lld\n",(an+n)%MOD); 80 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/quintessence/p/7464176.html

總結(jié)

以上是生活随笔為你收集整理的（组合数学）AtCoder Grand Contest 019 F - Yes or No的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。