这场比赛打得比较开心，而且觉得题比较有意思，记录下两道题解。
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;
        }
    }
}