TJ For 命中注定的抉择

· · 题解

出题人题解。

Sub1 显然答案为 \frac{n}{n+m}。
Sub2 是给深搜的，枚举每个盒子怎么放即可。
所以从 Sub3 开始讲。

Subtask #3

假设其中一个盒子共放置 s 个棋子，其中有 x 个黑子时概率最大。我们有 \frac{n-x}{n+m-s}+\frac{x}{s}\le \frac{n-1}{n+m-1}+1，因此一个盒子放一个黑子，剩下的放另一个盒子概率最大。

Subtask #4

考虑能否从 Sub3 的结论拓展，尽量每个黑子都只放一个盒子，正确性是肯定的。
每个盒子最多只能为答案提供 \frac{1}{a_1} 的贡献，一个黑子显然也是如此。而一个黑子如果选择和 x 个黑子，y 个白子放在一起只会为答案贡献 \frac{1}{a_1}(\frac{x+1}{x+y+1}-\frac{x}{x+y})，不如单独放一个盒子。

Subtask #5

现在，我们需要考虑有嵌套的情况。由于一开始我们已经选择了一些盒子只放黑子，现在在第二层的角度上完全可以把它们当作黑子，因为只要摸到它们就一定会摸到黑子。接下来就可以像之前一样放了。若 n 大于了 a_1，需要注意维护一个既有白子也有黑子的盒子，在第二层时把它当作白子即可（当然概率是要算其中黑子的）。

Subtask #6

我们把 k 层分成两部分，一部分是 a_i>n，这时没有黑子和白子放在一起；另一部分黑子和白子会放在一起，注意算有白子的盒子的贡献。然后注意判断当前在哪部分就行了。时间复杂度 O(k)，如果一直用费马小定理算逆元会多一个 \log，不一定可过，可以先预处理所有逆元降低复杂度。
当然，也可以用递归分治处理，不过空间复杂度较高，不宜 #define int long long。

Subtask #7

现在我们不能开数组预处理，但是可以把它压成一个变量，只需要单独维护分子和分母就行了。
这个 Sub 的意义是用来卡掉一些奇怪做法的。

Code

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const ll mod=998244353;
ll n,m,cn,cm,a,k,d,x;
inline ll inv(ll n){
    ll res=1,m=mod-2;
    while(m){
        if(m&1)res=res*n%mod;
        n=n*n%mod,m>>=1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>a>>d>>x;
    for(int i=1;i<=k;i++){
        if(a>n)m=a-n-!!cn;
        else
            if(m)cn=n-a+1,cm=m,n=a-1,m=0;
            else cn=((cn+cm)%mod*(n-a+2)%mod-cm+mod)%mod,n=a-1;
        a=a-d^x;
    }
    if(cn)cout<<(cn+(cn+cm)*n%mod)%mod*inv((cn+cm)*(n+1)%mod)%mod;
    else cout<<n*inv(n+m)%mod;
    return 0;
}