百度之星 2022 复赛 部分解题报告
省流:罚时上天,但是3题
A
签到题,注意到
C
考虑打表观察,我们发现有
-
对于
n 较小的情况,我们直接拉格朗日插值,这样是\mathcal{O}(n\log n) - 对于
m 较小的情况,我们暴力时间复杂度是\mathcal{O}(m\log n) 的
bound 可以设在
ll ffpow(ll a,ll b) {
ll ans = 1;
for (;b;b >>= 1) {
if (b & 1) ans = mul(ans,a);
a = mul(a,a);
}
return ans;
}
const int N = 5e6 + 10;
ll n,m,jc[N],inv[N],pr[N],pl[N];
namespace solver1 {
ll a[N];
void solve() {
ll x = 1,k = n - 1,y = 0,ans = 0;
jc[0] = inv[0] = pl[0] = pr[k + 3] = 1;
for (int i = 1;i <= k + 2;++i) {
jc[i] = jc[i-1] * i % mod;
pl[i] = pl[i-1] * (m - i) % mod;
}
for (int i = k + 2;i >= 1;--i) {
pr[i] = pr[i+1] * (m - i) % mod;
}
for(int i = 1; i <= k + 2; i ++) {
y = add(y,ffpow(i, k));
ll a = pl[i - 1] * 1ll * pr[i + 1] % mod;
ll b = jc[i - 1] * ((k - i) & 1 ? -1ll : 1ll) * jc[k + 2 - i] % mod;
b = add(b,mod);
ans = add(ans,y * a % mod * ffpow(b, mod - 2) % mod) % mod;
}
printf("%lld\n",mul(n,add(ans,mod)));
}
}
namespace solver2 {
void solve() {
ll ans = 0;
for (int i = 1;i <= m;++i) ans = add(ans,ffpow(i,n-1));
printf("%lld\n",mul(n,ans));
}
}
signed main() {
read(n,m);
if (n <= 1000000)solver1::solve();
else solver2::solve();
return 0;
}
D
考虑这个条件的限制,我们很自然想到把
考虑区间-子区间问题是一个 2-side 的问题,我们考虑用扫描线算法来解决。
具体来说,我们考虑当
我们讨论这四种的合并:
a 可以由左b 右c ,左a 右c 得到。b 可以由左a 右d ,左b 右b 得到。c 可以由左d 右a ,左c 右c 得到。d 可以由左d 右b ,左c 右d 得到。
于是直接暴力转移,题解写的好像是用矩阵维护转移?我猜大概是本质相同的东西。
总时间复杂度
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。