Preface
今天早上被公交车搞了，晚了30min才到……
最后T1读入\(n\)的时候写%d了，喜提30pts（结果Rank竟然不变233）
A. 「NOIP2022模拟赛二 By yzxoi A」『Pale』/ feat. 初音ミク
Pro
-
有线性递推数列\(F\)满足：
\[F(n)=3F(n-1)+2F(n-2)(n\ge 2)\\ F(0)=0,F(1)=1 \] -
\(Q\)次询问，每次询问\(F(n)\mod 998244353\)，强制在线
-
\(Q\le 10^7,n\le 10^{18}\)
Sol
以前学OI的时候推不来这种东西，现在参加完高考后发现还没平时做的题难……
首先构造等比数列求解，先待定个系数\(\alpha.\beta\)，有：
\[f(n)+\beta\cdot f(n-1)=\alpha\cdot (f(n)+\beta\cdot f(n-1))(n\ge 2)\\ \Leftrightarrow f(n)=(\alpha -\beta)\cdot f(n-1)+\alpha\beta\cdot f(n-2)(n\ge 2) \]由递推式解得：
\[\begin{cases}\alpha_1=\frac{3+\sqrt{17}}{2}\\\beta_1=\frac{\sqrt{17}-3}{2}\end{cases},\begin{cases}\alpha_2=\frac{3-\sqrt{17}}{2}\\\beta_2=-\frac{3+\sqrt{17}}{2}\end{cases} \]得到：
\[\begin{cases}f(n)+\beta_1\cdot f(n-1)=\alpha_1^{n-1}\cdot(f(1)+\beta_1\cdot f(0))\\f(n)+\beta_2\cdot f(n-1)=\alpha_2^{n-1}\cdot(f(1)+\beta_2\cdot f(0))\end{cases} \]联立消去\(f(n-1)\)得到\(f(n)=\frac{\alpha_2^n\beta_1-\alpha_1^n\beta _2}{\beta_1-\beta_2}=\frac{(\frac{3+\sqrt{17}}{2})^n-(\frac{3-\sqrt{17}}{2})^n}{\sqrt {17}}\)
然后由于数据范围很大我们需要\(O(1)\)快速幂，直接根号分治一下即可
#include<cstdio>
#define RI register int
#define CI const int&
#define CL const long long&
using namespace std;
const int mod=998244353,S=100000,sqrt_17=473844410;
int q,a1[S+5],ap1[S],a2[S+5],ap2[S],inv,cur,ans; long long n;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int QP(int *A,int *B,int p)
{
return 1LL*A[p%S]*B[p/S]%mod;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
inline int F(CL n)
{
return 1LL*sub(QP(a1,ap1,n%(mod-1)),QP(a2,ap2,n%(mod-1)))*inv%mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; scanf("%d%lld",&q,&n); inv=quick_pow(sqrt_17); a1[0]=a2[0]=ap1[0]=ap2[0]=1;
a1[1]=1LL*(3+sqrt_17)*quick_pow(2)%mod; a2[1]=1LL*(3-sqrt_17+mod)*quick_pow(2)%mod;
for (i=2;i<=S;++i) a1[i]=1LL*a1[i-1]*a1[1]%mod,a2[i]=1LL*a2[i-1]*a2[1]%mod;
for (i=1;i<S;++i) ap1[i]=1LL*ap1[i-1]*a1[S]%mod,ap2[i]=1LL*ap2[i-1]*a2[S]%mod;
for (ans=cur=F(n),i=2;i<=q;++i) n=n^(1LL*cur*cur),cur=F(n),ans^=cur;
return printf("%d",ans),0;
}
B. 「NOIP模拟赛二 By yzxoi B」Oval and Function
Pro
- 求不定方程\(x^2+3y^2=N^2\)的整数解的个数
- 数据组数\(T\le 10\)，\(n\le 10^{12}\)
Sol
刚开始写了个假算法求助陈指导被点破后发现这题两年前校内模拟赛做过，但我已经完全没有印象了的说
先讲一个假算法，刚开始考虑到利用平方换元法（也是高考中常用方法233），得到：
\[\begin{cases}x=k\cdot(m^2-3n^2)\\y=k\cdot(2mn)\\N=k\cdot(m^2+3n^2) \end{cases} \]其中\(k,m,n\)均为整数，只要枚举\(k|N\)然后再枚举\(n\)即可
但是这样并不能表示所有的情况，因为\(y\)显然只能是偶数
考虑正解，首先由于\(x=\pm n,y=0\)是显然成立的两组通解，而\(x=0\)时显然无解
并且若\((x,y),x,y\in N^*\)为一组解，那么\((x,-y),(-x,y),(-x,-y)\)也都是解
因此我们可以强制\(x,y\in N^*\)，最后把答案乘\(4\)再加\(2\)即可
考虑令\(a=N-x\)，则：
\[(N-a)^2+3y^2=N^2\Leftrightarrow -2Na+a^2+3y^2=0\Leftrightarrow 3y^2={a\cdot(2N-a)} \]设\(d=\gcd(a,2N-a)=\gcd(a,2N)\)，在上面的式子两边同时除以\(d^2\)得到
\[3(\frac{y}{d})^2=\frac{a}{d}\cdot \frac{2N-a}{d},(\gcd(\frac{a}{d},\frac{2N-a}{d})=1) \]互质的两数相乘是一个平方数的\(3\)倍，则这两个数必然一个是平方数，一个是某平方数的\(3\)倍
因此设\(\frac{a}{d}=3i^2,\frac{2N-a}{d}=j^2(i,j\in N^*,\gcd(3i,j)=1)\)（反之亦然），于是：
\[\frac ad+\frac{2N-a}d=3i^2+j^2\Leftrightarrow \frac{2N}d=3i^2+j^2 \]因此直接枚举\(d|2N\)，然后枚举\(i\)即可，复杂度上界是\(O(T\cdot n^{\frac{3}{4}})\)，显然跑不满
#include<cstdio>
#include<cmath>
#define RI register int
#define CI const int&
#define int long long
using namespace std;
int t,n;
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
inline int calc(CI x,int ret=0)
{
for (RI i=1;3LL*i*i<=x;++i)
{
int y=sqrt(x-3LL*i*i); if (y*y!=x-3LL*i*i) continue;
if (gcd(3LL*i,y)==1) ++ret;
}
return ret;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
int ans=0; scanf("%lld",&n); n<<=1; for (RI i=1;i*i<=n;++i)
if (n%i==0) if (ans+=calc(n/i),i*i!=n) ans+=calc(i);
printf("%lld\n",(ans<<2LL)+2);
}
return 0;
}
C. 「NOIP2022模拟赛二 By yzxoi C」『 だきしめるまで。』/ feat. 可不
Pro
- 给定一个\(n\)个点，\(m\)条边的有向图，\(q\)次询问从\(s\)到\(t\)经过至少\(k\)条边的最短路
- 数据组数\(T\le 10,2\le n\le 50,1\le m,k\le 10^4,1\le q\le 10^5\)
Sol
首先不难想到一个暴力做法，设\(f_{t,i,j}\)表示从\(i\)恰好经过\(t\)条边到\(j\)的最短路
但这样做因为\(k\le 10000\)显然是会爆炸的，考虑拆分问题
而这种拆分的方法一般就两种：倍增或根号分治，这道题显然不好倍增，因此考虑根号分治
设\(a_{t,i,j}\)表示从\(i\)至少经过\(t\)条边到\(j\)的最短路，\(pa_{t,i,j}\)表示\(i\)恰好经过\(100t\)条边到\(j\)的最短路
每次询问\(s\to t\)时考虑枚举一个中间点\(i\)，设\(p=k\operatorname{mod} 100,q=\lfloor\frac{k}{100}\rfloor\)，则答案就是
\[\min_\limits{1\le i\le n} (pa_{q,s,i}+a_{p,i,t}) \]复杂度\(O(100n^3+qn)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
#define CL const long long&
using namespace std;
const int N=55,S=105,INF=1e9;
int T,n,m,q,x,y,z,c[N][N],d[N][N],a[S][N][N],pa[S][N][N],tmp[N][N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&T);T;--T)
{
RI i,j,k,t; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) for (j=1;j<=n;++j)
c[i][j]=INF,a[0][i][j]=pa[0][i][j]=(i==j?0:INF);
for (i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&z),c[x][y]=min(c[x][y],z);
for (t=1;t<=100;++t) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
for (a[t][i][j]=INF,k=1;k<=n;++k) a[t][i][j]=min(a[t][i][j],a[t-1][i][k]+c[k][j]);
for (t=1;t<=100;++t) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
for (pa[t][i][j]=INF,k=1;k<=n;++k) pa[t][i][j]=min(pa[t][i][j],pa[t-1][i][k]+a[100][k][j]);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) d[i][j]=(i==j?0:c[i][j]);
for (k=1;k<=n;++k) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for (t=0;t<=100;++t)
{
for (i=1;i<=n;++i) for (j=1;j<=n;++j) tmp[i][j]=INF;
for (i=1;i<=n;++i) for (j=1;j<=n;++j) for (k=1;k<=n;++k)
tmp[i][j]=min(tmp[i][j],pa[t][i][k]+d[k][j]);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) pa[t][i][j]=tmp[i][j];
}
for (scanf("%d",&q);q;--q)
{
scanf("%d%d%d",&x,&y,&z); int p=z%100,q=z/100,ans=INF;
for (i=1;i<=n;++i) ans=min(ans,a[p][x][i]+pa[q][i][y]);
printf("%d\n",ans!=INF?ans:-1);
}
}
return 0;
}
D. 「NOIP2022模拟赛二 By yzxoi D」『くうになる』 / feat. 初音ミク ＆ 可不
Pro
-
给定长度为\(n\)的序列\(A\)，求：
\[\sum_{1\leq i < j\leq n}\max\{A_i,A_{i+1},\cdots,A_j\} [(A_i\&A_j)=A_j \lor (A_i\& A_j)=A_i] \] -
\(n\le 10^5,0\le A_i\le 10^{14}\)
Sol
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=10000005;
int n,a[N],rt; long long ans;
class Cartesian_tree
{
private:
struct CT
{
int ch[2],sz;
}node[N]; int stk[N],top,val,f[1<<15],g[1<<15],h[1<<15];
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
#define ch(x,y) node[x].ch[y]
#define sz(x) node[x].sz
inline void add(CI x,CI y)
{
int A=x>>7<<7,B=x&127; h[x]+=y; for (RI i=0;i<128;++i)
{
if ((B&i)==B) f[A|i]+=y; if ((B&i)==i) g[A|i]+=y;
}
}
inline void ask(CI x)
{
int A=x>>7,B=x&127; ans-=1LL*val*h[x]; for (RI i=0;i<=128;++i)
{
if ((A&i)==i) ans+=1LL*val*f[(i<<7)|B];
if ((A&i)==A) ans+=1LL*val*g[(i<<7)|B];
}
}
inline void modify(CI now,CI v)
{
add(a[now],v); if (lc(now)) modify(lc(now),v); if (rc(now)) modify(rc(now),v);
}
inline void query(CI now)
{
ask(a[now]); if (lc(now)) query(lc(now)); if (rc(now)) query(rc(now));
}
public:
inline void build(void)
{
for (RI i=1;i<=n;++i)
{
while (top&&a[i]>a[stk[top]]) --top;
if (top) lc(i)=rc(stk[top]),rc(stk[top])=i;
else lc(i)=stk[top+1]; stk[++top]=i;
}
rt=stk[1];
}
inline void getsz(CI now=rt)
{
if (sz(now)=1,lc(now)) getsz(lc(now)),sz(now)+=sz(lc(now)); if (rc(now)) getsz(rc(now)),sz(now)+=sz(rc(now));
}
inline void DSU(CI now=rt)
{
int d=sz(lc(now))<sz(rc(now));if (ch(now,d^1)) DSU(ch(now,d^1)),modify(ch(now,d^1),-1);
if (ch(now,d)) DSU(ch(now,d)); add(a[now],1); val=a[now]; ask(a[now]);
if (ch(now,d^1)) query(ch(now,d^1)),modify(ch(now,d^1),1);
}
#undef lc
#undef rc
#undef ch
#undef sz
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),ans-=a[i];
return T.build(),T.getsz(),T.DSU(),printf("%lld",ans),0;
}