话题
主题背景
“要想成为标杆,绝对没有捷径;成为标杆之后,就没有回头路了!” 从未忘记自己的使命。 “所谓标杆,就是为走在大家面前的人,忍受所有的赞美!”
我最大的错误是试图与进行比较。有些错误需要一辈子来偿还。
主题描述
日,有概率参加考试,然后被超越;也有不参加考试的概率,什么都不会发生。如果在天后,至少被超过,则称为“太阳东打西出”。
现在求所有满足的的“太阳从东方出来”的概率之和。
数据范围和提示
但。输入中还给出了一个非负整数,使得和。 等范围的其余部分是无用的。输出为模⒒。
想法
有一种奇怪的情况。它将在哪里使用?
在求解或的子任务时,发现解的总数的计算可以是,那么分子实际上是关于的多项式,长度不超过。最后乘以一个,就可以解出一个简单的数字组合。
继续做好工作,继续思考生成函数。可以看出,当前和“已经获得的keys”的个数是有用的,独立的,所以需要写成二进制生成函数
那么答案是。如何解决这个问题?
显然我们要保留分子的指数,所以分母要分开记录。也就是说,用的分母记录多项式(分子)。
然后我们依次做乘法,得到的结果相当于分母为时求的系数。既然是过渡,复杂度当然是状态数。
最后需要除以,相当于乘以和,也就是乘以
不幸的是,我们必须计算。也就是枚举出和的指数后,我们面临的问题其实是
因为的指标不小于某个阈值。由于的范围是,所以一定不能这样计算。怎么做?
建议:组合数应递归计算。比如这个问题。虽然这看起来不太合乎逻辑。
上式也可以写成。为方便递归,可简写
即用代替。 这里没有设置为自变量,因为在后面的递归中两者不变。
最简单的方法:使用帕斯卡定律减少上指标。比如把换成,前者换成,后者换成。这相当于在坐标系中沿着四连通边移动;只需要选择一个边界。由于是下标,必然有,取边界。但是可以取任何值。观察到可以最小化计算量。
- ,那么
最后一步可以从的组合含义得到:在元素之后,插入一个选中的元素。或者,只需交换第一行的下标,即可获得具有二项式系数的简单卷积恒等式。
- ,那么
因为左手形式只在时产生非零值。
枚举边界值,考虑它们对的贡献,然后
注意“在坐标系中行走”的系数是,因为不能再通过了。
这是的枚举,所以总的时间复杂度是,!
再聊几句:原来的公式有一个组合的意思,即第一个框放球,后面框放球,可以为空的方案数。唯一的限制是,即前格中至少有个球。
好主意:改为枚举第个球的位置。设为第框,则第一个球也在这个框内;最后一个球在最后一个盒子里,所以
你会发现它和完全一样,只是中列举的就是这里的。所以上面的代数演绎是不必要的,组合的意义有时比数学演绎要好。恰恰是因为它恰好有这样的综合意义,才可以通过数学推导得到一个简单的公式!
代码
#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
int a = 0; int c = getchar(), f = 1;
for(; !isdigit(c); c=getchar())
if(c == '-') f = -f;
for(; isdigit(c); c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
const int MAXN = 105, MOD = 998244353;
int inv[MAXN];
inline int getC(int n, int m){
llong c = 1;
for(int i=0; i!=m; ++i)
c = c*(n-i)%MOD*inv[i+1]%MOD;
return int(c);
}
inline int calc(int n1, int m1, int n2, int m2){
if(m1 == -1) return n1 ? 0 : int(getC(n2+m2,m2)); // m2 != -1
static int t1[MAXN], t2[MAXN]; int res = 0;
t1[0] = 1, t2[0] = getC(m2+n2+1,m2+1);
rep(j,1,m1) t1[j] = int(llong(n1+j-1)*t1[j-1]%MOD*inv[j]%MOD);
rep(j,1,m1) t2[j] = int(llong(m2+n2+1+j)*t2[j-1]%MOD*inv[j+m2+1]%MOD);
rep(j,0,m1) res = int((res+llong(t1[j])*t2[m1-j])%MOD);
return res;
}
int dp[2][MAXN][MAXN][MAXN];
int main(){
int m = readint(), d = readint();
int N = readint(), n = readint();
rep(i,(inv[1]=1)+1,m) inv[i] = int(
llong(MOD-MOD/i)*inv[MOD%i]%MOD);
const int Nd = N/d;
****dp = 1; // x^0 y^0
for(int i=1,fr=0,a; i<=m; ++i,fr^=1){
a = (readint()+1)/d; llong p = readint();
rep(j,0,i) rep(x,0,Nd) rep(y,0,x){
int &v = dp[i&1][j][x][y] = int( (
(x < a ? 0 : (p-1)*dp[fr][j][x-a][y])
+ (MOD+1-p)*dp[fr][j][x][y] ) %MOD );
if(!j) break; // cannot choose it here
v = int((v+p*dp[fr][j-1][x][y])%MOD);
if(x >= a && y >= a) v = int((v+
(MOD-p)*dp[fr][j-1][x-a][y-a])%MOD);
}
}
int ans = 0;
rep(a,0,m) rep(x,0,Nd) rep(y,0,x) if(dp[m&1][a][x][y]){
const int l = std::max(0,n-y*d);
if(l > N-x*d) continue; // invalid
ans = int((ans+llong(dp[m&1][a][x][y])
*calc(l,a-1,N-x*d-l,m-a-1))%MOD);
}
printf("%d\n",ans);
return 0;
}
版权声明:本文为博主OneInDark原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_42101694/article/details/123047901