CF1731B题解

千早爱音 · 2022-12-28 08:38:25 · 题解

证明参考了官方题解。

我们的最优策略是每次向右向下移动，则答案为 \sum_{i=1}^n i^2+\sum_{i=1}^{n-1}i\times (i+1)=\frac{n(n+1)(4n+1)}{6} 。

这个数列是 OEIS A002412，直接套公式即可。

接下来证明为什么这样是对的：

设 d_{i,j} 表示到达 (i,j) 时候的最大答案， a_{a,b,c,d} 表示从 (a,b) 到 (c,d) 的路径长度，在下面的假设中总是保证路径唯一。

则显然有 d_{n-1,n-1} \geq d_{i,n-1}+a_{i+1,n-1,n-1,n-1}=d_{i,n-1}+\frac{(n-1-i)(n-1)^2}{2} 。

设 f_{i,j} 表示经过某个边界 (i,n) 到达 (n,n) 的最大答案， ans_{i,j} 表示按照上述策略行走路线得到的最大答案。则显然有 ans_{n,n}=d_{n-1,n-1}+n \times (n-1)+n^2,f_{n,n}=d_{i,n-1}+a_{i,n,n,n}=\frac{(n+1-i)(n+i)n}{2},d_{n,n}-f_{n,n}=d_{n-1,n-1}+n \times (n-1) + n^2-d_{i,n-1}-\frac{(n-1-i)(n-1)^2}{2} ，来自上面推出的式子。

于是 ans_{n,n}-f_{n,n} \geq d_{i,n-1}+\frac{(n+1-i)(n+i)n}{2}+n \times (n-1) + n^2-d_{i,n-1}-\frac{(n-1-i)(n-1)^2}{2} ，消去 d_{i,n-1} ，有 ans_{n,n}-f_{n,n} \geq \frac{(n+1-i)(n+i)n}{2}+n \times (n-1) + n^2-\frac{(n-1-i)(n-1)^2}{2}=\frac{2n^2-3n-n \times i-i-1}{2} 。

这里首先有当 i 在区间 [1,n-2] 中的时候，不难证明 \frac{2n^2-3n-n \times i-i-1}{2}\geq 0 ，所以发现 ans_{n,n} \geq f_{n,n} ，按照这个方法构造总是最优，得证。

关于取模问题：

首先不难发现 2022 是 6 的倍数，直接乘上 337 即可，当然这里是用乘法逆元实现。

时间复杂度 \mathcal{O}(T) ，可以通过。

代码：

#import <bits/stdc++.h>
using namespace std;
#define int long long
int p[4000040];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int ksm(int a,int b,int mod)
{
    int res=1;
    while(b)
    {
        if(b&1)
        res=res*a,res%=mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int sum[20000020];
const int mod=1e9+7;
signed main() 
{
    int T;
    cin>>T;
    while(T--) 
    {
        int n;
        cin>>n;
        int ans=n*(n + 1)%mod*(4*n - 1)%mod*ksm(6,mod-2,mod)%mod;
        cout<<ans*2022%mod<<'\n';
    }
}