Codeforces Round #841 (Div. 2) and Divide by Zero 2022
o(╥﹏╥)o
2022的最后一场也没打好
B题反正我是理解错了，我看到题目上写着要相乘再取模，结果就真的去先乘再取模，这样想都不用想会爆，真无语，反正B没写好我后面的也不想看了，C题也没怎么看就直接看答案了（不过要是我看了也不会想到那么巧妙的解题方法的）
B
还有一点我没有做出来的一点是，我推出了答案是
\[\sum_{i=1}^{n}i^{2}\ +\sum_{i=1}^{n-1}i(i+1) \]而我就好像只知道第一个怎么推导，后面一个我竟然用循环求答案（现在想起就无语，这真的是我吗）
然后我换了一种策略，我发现题目给的案列的答案最后一个不能被2022整除，于是我就异想天开，以为后面的答案都是同一个数（我脑子呢，后面还要取余呀）
以上是我的愚蠢行为
\[2\sum_{i=1}^{n}i^{2}\ +\sum_{i=1}^{n}i-n(n-1) \]后面我发现上面那一个公式可以推导为
这样就很好算了（括号是个很麻烦的东西，但需要求累和的时候，尽量把括号解决）
还有，在求这个答案的时候可以取余的哦，不要被题目后面的话误导了
还有一个问题是我在求这一个答案中和队友们想明白的问题
就是在一个既有取余，又有除法的求值过程中，如果直接按照乘法的那种直接取余
如
6%4/3和6/3%4答案是不同的，取余后和取余前除出来的数不同
我想起以前看到一些大佬求除法都是以逆元的形式，以前想不明白，现在想起觉得任何事都有它的理由，现在可能不知道，到后面你有可能就会明白了，这种感觉太妙了
#include <iostream>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,t;
int two,three;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if (p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res;
}
int fun(int n)
{
int ans=n*(n+1)%mod*(2*n+1)%mod*three%mod;
ans=(ans-(n*(n+1)%mod*two%mod));
ans=(ans%mod+mod)%mod;
ans=(ans*2022)%mod;
return ans;
}
void solve()
{
cin>>n;
cout<<fun(n)<<'\n';
return ;
}
signed main ()
{
cin>>t;
two=ksm(2,mod-2);
three=ksm(3,mod-2);
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这道题我感觉妙不可言的地方就在它运用了正难则反的思想
还用到了“前缀和”来求一段的异或值
其他的看代码感受
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int maxn=2e5+10;
#define int long long
int n,t;
void solve()
{
cin>>n;
vector<int> a(n+1), cnt(2 * n+2);//cnt[i]，数字i出现的次数
cnt[0]++;//从1开始的
long long ans=n*(n+1)/2;//一共有这么多种，下面我们通过寻找不符合条件的来求出最后所有符合条件的，
int pp=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i-1]^a[i];//a[i]代表从1到i的异或值，异或的前缀和
for (int j=0;j*j<=2*n;j++)
{
int now=j*j;//平方数一定只有奇数个因子
int p=now^a[i];//p^a[i]==now，p也是一个前缀和，而且是在a[i]前面的，假如p是a[k]，那么这一段就是K+1到i这一段的异或值是now
if (p>2*n) break;
pp+=cnt[p];//我们要减去不符合条件的（cnt是p出现过的）
}
cnt[a[i]]++;//此时a[i]出现过一次
}
cout<<ans-pp<<'\n';
return ;
}
signed main ()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
还有一个气愤的是我cnt用 map存就超时了，后来查了一下，map的查询是O（logn)，而数组是O（1）
D
这一道题的存数组的大小不好控制，我这里用了二维vector
然后但一个l是满足条件的时候，比l小的一定是满足条件的，由此，这一道题可以用二分来做
而且，这一道题还用到了二维前缀和，来判断这一个区域是不是都>l
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
int n,t,m;
bool check(int x,vector<vector<int>>c)
{
vector<vector<int>>b(n+1,vector<int>(m+1));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
int now=0;
if (c[i][j]>=x) now=1;
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+now;
}
}
for (int i=x;i<=n;i++)
{
for (int j=x;j<=m;j++)
{
int now=b[i][j]-b[i][j-x]-b[i-x][j]+b[i-x][j-x];
if (now==x*x) return true;
}
}
return false;
}
void solve()
{
cin>>n>>m;
vector<vector<int>>a(n+1,vector<int>(m+1));
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int l=1,r=min(n,m)+1;
int ans=-1,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (check(mid,a))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}