[ARC147D] Sets Scores
将 \(S_i\) 相对于 \(S_{i-1}\) 的变化看作一次改变某个元素存在状态的操作。
观察到对于同一个操作序列初始选取和不选取第一个数的贡献和为 \(n\)。
那记对于某个操作序列考虑 \(i\) 个元素的答案为 \(f_i\)，有 \(f_i=f_{i-1}\times n\)。
所以对于任意一个操作序列答案均为 \(n^m\)，又一共有 \(m^{n-1}\) 种操作序列，所以答案为 \(n^mm^{n-1}\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int mod=998244353;
int quick_pow(int x,int y,int res=1){for(;y;x=x*x%mod,y>>=1) if(y&1) res=res*x%mod;return res;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n>>m,cout<<quick_pow(n,m)*quick_pow(m,n-1)%mod;
}
[CERC2015] Frightful Formula
第 \(i\) 行第 \(1\) 列元素的贡献：\(\binom{2n-i-2}{i-2}\times a^{n-1}\times b^{n-i}\times x\)。
第 \(1\) 行第 \(j\) 列元素的贡献：\(\binom{2n-j-2}{j-2}\times a^{n-j}\times b^{n-1}\times x\)。
第 \(i\) 行第 \(j\) 列加 \(c\) 的贡献：\(\binom{2n-i-j}{n-i}\times a^{n-j}\times b^{n-i}\times c\)。
优化 \(c\) 贡献的求和过程即可，手推了一遍不想敲公式了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define LL long long
const LL mod=1000003;
LL n,a,b,c,ans,sum,dp[N],poa[N],pob[N],pab[N],fac[N],inv[N];
LL quick_pow(LL x,LL y,LL res=1){for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;return res;
}
LL C(LL n,LL m){return (n<m)?0:fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){scanf("%lld%lld%lld%lld",&n,&a,&b,&c),fac[0]=inv[0]=poa[0]=pob[0]=pab[0]=1;for(int i=1;i<=n*2;i++) poa[i]=poa[i-1]*a%mod;for(int i=1;i<=n*2;i++) pob[i]=pob[i-1]*b%mod;for(int i=1;i<=n*2;i++) fac[i]=fac[i-1]*i%mod;for(int i=1;i<=n*2;i++) pab[i]=pab[i-1]*(a+b)%mod;for(int i=0;i<=n-2;i++) sum=(sum+pab[i])%mod;for(int i=1;i<=n*2;i++) inv[i]=quick_pow(fac[i],mod-2);for(int i=1,x;i<=n;i++){scanf("%d",&x);if(i==1) continue;ans=(ans+C(2*n-i-2,n-i)*poa[n-1]%mod*pob[n-i]%mod*x)%mod;}for(int i=1,x;i<=n;i++){scanf("%d",&x);if(i==1) continue;ans=(ans+C(2*n-i-2,n-i)*poa[n-i]%mod*pob[n-1]%mod*x)%mod;}for(int i=1;i<=n-2;i++) dp[n-1]=(dp[n-1]+C(n-1,i)*pob[i]%mod*poa[n-i-1])%mod;for(int i=n;i<=n*2-4;i++){dp[i]=dp[i-1]*(a+b)%mod;dp[i]=(dp[i]-C(i-1,n-2)*poa[i-n+1]*pob[n-1]%mod+mod)%mod;dp[i]=(dp[i]-C(i-1,i-n+1)*poa[n-1]*pob[i-n+1]%mod+mod)%mod;}for(int i=n-1;i<=n*2-4;i++) sum=(sum+dp[i])%mod;printf("%lld\n",(ans+sum*c)%mod);
}
[ARC139D] Priority Queue 2
考虑差分计算贡献，令 \(a_i\) 表示 \(\geq i\) 的数的个数，答案显然等于 \(\sum a_i\)。
加入一个数 \(x\) 相当于将 \(a_1,a_2,\cdots,a_x\) 加 \(1\)，删除第 \(k\) 小相当于将 \(>n-k+1\) 的 \(a_i\) 减 \(1\)。
考虑计算 \(a_i\) 被加了 \(j\) 次的贡献，令 \(k'=n-k+1\)：
若初始 \(a_i\leq k'\)，则最后 \(a'_i=\min(a_i+j,k')\)，因为当 \(a_i\) 大于 \(k'\) 的时候会马上被减掉。
若初始 \(a_i> k'\)，则最后 \(a'_i=\max(a_i-n+j,k')\)，因为当 \(a_i\) 小于等于 \(k'\) 时就不会被减了。
然后枚举 \(i\) 和 \(j\)，组合系数为有 \(j\) 个 \(\geq i\) 的方案数，即 \(\binom{n}{j}\times (m-i+1)^j\times (i-1)^{n-j}\)。