P5014 水の三角(修改版)
题意
现在我们定义一个三角图是像上面一样的图。。
请求出一个无限大的三角图从 1 号点走到 \(u\) 号点的方案数。
有 \(T\) 组询问。
分析
首先我们查看操作对我们当前位置的影响。
左下：\((1,0)\)；右下：\((1,1)\)；右：\((0,1)\)。
易得枚举往左下或者右下走的次数是比较方便的。易发现枚举往右下走的次数更好，因为不影响边界。而后若假设枚举了往右下走的次数 \(k\)，那么我们显然有左下 \(x-k\) 步，右下 \(k\) 步，右 \(y-k\) 步。则右下走的方案数：\(C_{x+y-k}^{k}(k∈[0,\min(x,y) ])\)。而后我们此时有：从 \((0,0)\) 走到 \((x-k,y-k)\) ，每步可以走 \(x\) 或 \(y\)，要求过程中\(y≤x\)，求方案数\(f(k)\)。则我们使用计算卡特兰数模板的方法，我们把不合法的路径都映射到从 \((0,0)\) 走到 \((y-k-1,x-k+1)\) 的路径上。则可由组合数的意义得\(f(k)=C_{x+y-2k}^{x-k}-C_{x+y-2k}^{x-k+1}\)。则我们可以由乘法原理得总贡献为右下方案数乘上合法其他路径方案数。则有\(Ans=\sum_{k=0}^{\min(x,y)}C_{x+y-k}^{k}·f_{k}\)。考虑使用快速幂+逆元维护组合数。别忘了处处取模。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int mod=998244353;
struct node{
int inv[2000090],fac[2000090];
int qpow(int shu,int cifang){
int ans=1;int k=cifang;
while(k){
if(k&1){ans=ans*shu%mod;ans%=mod;shu=shu*shu%mod;shu%=mod;}
else{shu=shu*shu%mod;shu%=mod;}
k>>=1;
}
return ans%mod;
}
void init(int len){
fac[0]=1;
for(int i=1;i<=len;i++) fac[i]=fac[i-1]*i%mod;
inv[len]=qpow(fac[len],mod-2);
for(int i=len;i;i--){
inv[i-1]=inv[i]*(i)%mod;
}
}
int C(int n,int m){
// printf("%d %d\n",n,m);
// printf("%d",fac[n]%mod*inv[m]%mod*inv[n-m]%mod);
return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
}lg_get;
int f(int x,int y,int k){
int ans=lg_get.C(x+y-2*k,x-k)%mod-lg_get.C(x+y-2*k,x-k+1)%mod;
ans+=mod,ans%=mod;
return ans;
}
void solve(){
scanf("%lld",&n);
int a=sqrt(n)-1,k;
while(n-(long long)a*(a-1)/2>a)a++;
k=n-(long long)a*(a-1)/2;
// int x=k,y=a;
int y=k,x=a;
x--,y--;
// printf("%lld %lld\n",x,y);
int ans=0;
for(int kk=0;kk<=min(x,y);kk++){
// printf("%d\n",kk);
int tmp=lg_get.C(x+y-kk,kk)%mod*f(x,y,kk)%mod;
tmp%=mod;
// printf("%lld\n",tmp);
ans+=tmp;
ans%=mod;
}
printf("%lld\n",ans);
}
const int MAXN=1e6+7;
signed main(){
lg_get.init(MAXN*2);
int T;
cin>>T;
while(T--) solve();
}
[ABC205E] White and Black Balls
题意
给出 \(n\) 个白球，\(m\) 个黑球及一个常数 \(k\)，问有多少种排列使得 \(\forall i\in[1,n+m],w_i\le b_i+k\)，其中 \(w_i\) 表示在排列的第 \(i\) 个球以及它之前的白球个数，\(b_i\) 表示在排列的第 \(i\) 个球以及它之前的黑球个数。
分析
我们转换一下题目条件可以得 \(b_{i}-w_{i}≥-k\)。而后我们可以把问题转化为从数轴原点出发，要求向右走 \(m\) 步，向左走 \(n\) 步，并且不越过 \(-k\)。我们不考虑限制条件那么所有的操作方案数为 \(C_{n+m}^n\)。
而后我们考虑这个**不越过 \(-k\) **的限制条件。显然有所有不合法操作都会抵达 \(-k-1\)。那么我们把所有这一时刻后的不合法操作以 \(-k-1\) 为对称轴取反。则有最后我们经过一些操作，由原来的终点 \(n-m\) 变为 \(n-m-2(k+1)\)。我们设向右走\(R\)步且为正贡献1，向左走 \(L\) 步且为负贡献1。则有二元一次方程组
\(①：L+R=n+m\)。
\(②：R-L=n-m-2(k+1)\)。
那么我们解得
\(L=m+k+1,R=n-k-1\)。则有不合法路径数 \(C_{n+m}^{m+k+1}\)。
于是答案为 \(C_{n+m}^{n}-C{n+m}^{m+k+1}\)。我们可以使用快速幂+逆元求算组合数。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct node{
const int mod=1e9+7;
int inv[2000005],fac[2000005];
int qpow(int shu,int cifang){
int ans=1;int k=cifang;
while(k){
if(k&1){ans=ans*shu%mod;ans%=mod;shu=shu*shu%mod;shu%=mod;}
else{shu=shu*shu%mod;shu%=mod;}
k>>=1;
}
return ans%mod;
}
void init(int len){
fac[0]=1;
for(int i=1;i<=len;i++) fac[i]=fac[i-1]*i%mod;
inv[len]=qpow(fac[len],mod-2);
// printf("%lld",inv[n+m]);
for(int i=len;i;i--){
inv[i-1]=inv[i]*(i)%mod;
}
}
int C(int n,int m){
return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
}lg_get;
int k;
signed main(){
cin>>n>>m>>k;
lg_get.init(2000000);
if(n>m+k) return printf("0"),0;
int ans=lg_get.C(n + m, m) - lg_get.C(n + m, m+k+1);
ans+=lg_get.mod;
ans%=lg_get.mod;
printf("%lld",ans);
}
[CF1204E] Natasha, Sasha and the Prefix Sums
题意
一个长度为 \(n+m\)，有 \(n\) 个 \(1\) 和 \(m\) 个 \(-1\) 的序列 \(a\)，定义其最大前缀和为： $$\large \max{ 0,\max\limits_{1\le i\le n+m}\sum\limits_{j=1}^ia_j }$$。求算所有可能序列的最大前缀和。
分析
首先我们考虑一种计算总贡献的方法，首先我们有一种朴素的想法，即我们枚举状态 \(s\) 时，求算\(\sum f(s)\)，但是这道题显然我们不能暴力枚举每种情况，我们考虑另外一种情况，若设某个序列的贡献为 \(val\) 时，我们可以使用 \(\sum Cnt_{val}*val\)来求解。
对于这道题我们可以使用后者来求解，我们考虑前缀和区间以及题目中的定义，显然有 \(val∈[\max(1,n-m),n)\)。而后我们可以考虑使用类似Catalan数的方法进行求解，我们考虑把序列中的 \(1\) 看做向右走，序列中的 \(-1\) 看做向左走，则有最大前缀和为过程中坐标的最大值，则我们考虑一种 \(f(k)\) 表示不向右越过 \(k\) 的方案数，则有 \(f(k)\) 表示最大前缀和小于等于\(k\)的方案数，显然我们有最大前缀和的方案数为\(f_k-f_{k-1}\)。而后我们考虑单个Catalan序列的求解。
我们不考虑限制条件那么所有的操作方案数为 \(C_{n+m}^m\)。
而后我们考虑这个**不越过 \(k\) **的限制条件。显然有所有不合法操作都会抵达 \(k+1\)。那么我们把所有这一时刻后的不合法操作以 \(k+1\) 为对称轴取反。则有最后我们经过一些操作，由原来的终点 \(n-m\) 变为 \(2(k+1)-n+m\)。我们设向右走\(R\)步且为正贡献1，向左走 \(L\) 步且为负贡献1。则有二元一次方程组
\(①：L+R=n+m\)。
\(②：R-L=2(k+1)-n+m\)。
那么我们解得
\(L=n-k-1,R=m+k+1\)。则有不合法路径数 \(C_{n+m}^{m+k+1}\)。
则有\(f(k)=C_{n+m}^{m}-C_{n+m}^{m+k+1}\)。
我们考虑总贡献有\(Ans=\sum_{k=\max(1,n-m)}^{n}k·(f(k)-f(k-1))\)。
我们考虑使用快速幂+逆元求算组合数。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int mod=998244853;
struct node{
int inv[2000090],fac[2000090];
int qpow(int shu,int cifang){
int ans=1;int k=cifang;
while(k){
if(k&1){ans=ans*shu%mod;ans%=mod;shu=shu*shu%mod;shu%=mod;}
else{shu=shu*shu%mod;shu%=mod;}
k>>=1;
}
return ans%mod;
}
void init(int len){
fac[0]=1;
for(int i=1;i<=len;i++) fac[i]=fac[i-1]*i%mod;
inv[len]=qpow(fac[len],mod-2);
for(int i=len;i;i--){
inv[i-1]=inv[i]*(i)%mod;
}
}
int C(int n,int m){
return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
}lg_get;
int f(int n,int m,int k){
int ans=lg_get.C(n+m,m)%mod-lg_get.C(n+m,m+k+1)%mod;
ans+=mod,ans%=mod;
return ans;
}
void solve(){
scanf("%lld%lld",&n,&m);
// int x=k,y=a;
// int y=k,x=a;
// x--,y--;
// printf("%lld %lld\n",x,y);
int ans=0;
for(int kk=max(1ll,n-m);kk<=n;kk++){
// printf("%d\n",kk);
int tmp=kk%mod*(f(n,m,kk)-f(n,m,kk-1))%mod;
tmp%=mod;
// printf("%lld\n",tmp);
ans+=tmp;
ans+=mod;
ans%=mod;
}
printf("%lld\n",ans);
}
const int MAXN=1e6+7;
signed main(){
lg_get.init(MAXN*2);
// int T;
// cin>>T;
// while(T--) solve();
solve();
}