这场比赛打得比较开心,而且觉得题比较有意思,记录下两道题解。
Dashboard - Codeforces Round #736 (Div. 2) - Codeforces
D
题意
给定n个数,找到其中一个连续的区间,满足有相同的余数,使得这样的区间最大。
题解
“简洁性是真理的标志”。对原数组进行差分后维护每个区间的gcd,暴力每个区间找到长度最大的区间即可。为了维护每个区间的gcd并且快速查询,ST表是最合适的。听说线段树和树状数组也能过,不过复杂度肯定比ST表高。
代码
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
const int maxn=2e5+10;
ll a[maxn],st[maxn][25],t,n;
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr);
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++)st[i][0]=abs(a[i+1]-a[i]);
for(int i=1;i<=__lg(n);i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=__gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
ll j=1,ans=1;
for(int i=1;i<n;i++){
ll len=__lg(i-j+1);
while(j<=i&&__gcd(st[j][len],st[i-(1<<len)+1][len])==1)j++,len=__lg(i-j+1);
ans=max(ans,i-j+2);
}
cout<<ans<<endl;
}
return 0;
}
E
题意
每分钟来3只小猪,狼每次吃x个,总共n分钟,问有几种吃法。
题解
显然是个组合数问题,更准确说就是求\sum \limits_{i}^{n} C^x_{3i}。然而求组合数普通就得花O(n)的时间,再求和又是O(n),无法承受。我们可以发现其中有很多运算被重复计算了,如果能够记忆这些运算肯定能够减小复杂度,所以dp是可以的,时间复杂度应该是O(nlogn)。
但更妙的做法是构造一个多项式P(k)=(1+k)^3+(1+k)^6+\cdots+(1+k)^{3n},其中k^x的系数就是要求的答案。(二项式定理)时间复杂度O(n)。
而且由于构造的多项式是一个几何级数,所以不需要使用FFT,直接使用求和公式可得P(k)=\frac{(1+k)^{3N+3}-(1+k)^3}{(1+k)^3-1}。(错位相减可得求和公式)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000010;
const int MOD = 1e9+7;
ll frac[3*MAXN], comb[3*MAXN], reci[3*MAXN], ans[3*MAXN];
ll pw(ll a, int b) {
if(b==0) return 1;
ll x=pw(a*a%MOD,b>>1);
if(b&1) x = (x*a)%MOD;
return x;
}
int main() {
ios::sync_with_stdio(false);
int T = 1;
while(T--) {
int n, q;
cin >> n >> q;
frac[0] = frac[1] = 1;
for(int i = 2; i <= 3*n+3; i++) {
frac[i] = (frac[i-1] *i) %MOD;
}
reci[3*n+3] = pw(frac[3*n+3], MOD-2);
for(int i = 3*n+2; i >= 0; i--)
reci[i] = (reci[i+1] * (i+1)) % MOD;
for(int i = 0; i <= 3*n+3; i++)
comb[i] = frac[3*n+3]*(reci[i]*reci[3*n+3-i]%MOD)%MOD;
ll x = pw(3, MOD-2);
ans[0] = n+1;
ans[1] = (comb[2]*x%MOD - ans[0]+MOD)%MOD;
for(int i = 2; i <= 3*n; i++)
ans[i] = ((comb[i+1]-ans[i-2]-3*ans[i-1])%MOD+MOD)%MOD*x%MOD;
while(q--) {
int i;
cin >> i;
cout << ans[i] << endl;
}
}
}
Comments | NOTHING