6.15 NOI 模拟
\(T1\ ckr\)与平方数
不会吧，不会吧，真有人不会积分，好吧，我真的一点也不会。。。
基本公式\(:\)
\(1.\)多项式定积分的计算方法
\[f(x)=\sum_{i=0}^nc_ix^i \\ \int_{a}^{b}=\sum_{i=0}^n\frac{(b^{i+1}-a^{i+1})c_i}{i+1} \]\(2.\)换元积分法
设\(I\subseteq \R\)为一个区间，\(\varphi:[a,b]\rightarrow I\)是一个导数可积的函数(不是数论函数)。设\(f:I\rightarrow \R\)是一个连续函数。(说人话就是连续可导)
\[\int_a^b f(u){\rm d}u=\int_{\varphi(a)}^{\varphi(b)}f(\varphi(x))\varphi'(x){\rm d}x \]考虑证明：
设\(F'(x)=f(x)\)
\[\int f(u) {\rm d}u=F(u)+C \\ u=\varphi(x) \\ {\rm d}[F(u)]={\rm d}[F(\varphi(x))]=f(\varphi(x))\varphi'(x) {\rm d}x \\ \int f(\varphi(x))\varphi'(x) {\rm d}x=\int f(u){\rm d}u \]\(3.\)分部积分法
设\(u=u(x),{\rm d}u=u'(x){\rm d}x,v=v(x),{\rm d}v=v'(x){\rm d}x\)
\[\int_a^b u(x)v'(x){\rm d}x=[u(x)v(x)]_a^b-\int_a^b u'(x)v(x) \]考虑证明：
\[[u(x)v(x)]'=u'(x)v(x)+u(x)v'(x) \\ [u(x)v(x)]'-u'(x)v(x)=u(x)v'(x) \]两边分别积分即可
\[u(x)v(x)-\int u'(x)v(x)=\int u(x)v'(x) \]然后做这道题：
算法一
假如我们只看懂了第一个式子(就像我一样)
暴力卷积求出每一项系数积回去即可
#define Eternal_Battle ZXK
#include
#define int long long
#define MAXN 3005
using namespace std;
const int mod=2147483647;
int a[MAXN],b[MAXN],c[MAXN<<1],fx[MAXN<<1],inv[MAXN<<1];
int N,s,t,x;
void sol(int n,int m)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
a[0]=s; a[1]=1;
b[0]=t; b[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=i;j>=1;j--)
{
a[j]=(a[j-1]+a[j]*s%mod)%mod;
}
(a[0]*=s)%=mod;
}
for(int i=2;i<=m;i++)
{
for(int j=i;j>=1;j--)
{
(b[j]=b[j-1]+b[j]*t%mod)%=mod;
}
(b[0]*=t)%=mod;
}
memset(c,0,sizeof(c));
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
(c[i+j]+=a[i]*b[j]%mod)%=mod;
}
}
int res=0;
for(int i=0;i<=n+m;i++)
{
res=(res+(fx[i+1]*c[i])%mod*inv[i+1]%mod)%mod;
}
printf("%lld ",res);
}
void Init()
{
fx[0]=1; fx[1]=x;
inv[0]=inv[1]=1;
for(int i=2;i 算法二
使用\(FFT\)计算系数，分数不变
算法三
\(s=t\)，可以直接套用公式
\[\int (x+t)^n {\rm d}x=\frac{(x+t)^{n+1}}{n+1}+C \]算法四
我们看懂了第二条和第三条公式，但是我们不想往下推了！
\(x\leftarrow x+s\)
\[\int_0^{x_0}(x+s)^n(x+t)^m {\rm d}x=\int_s^{x_0+s}x^n(x+t-s)^m{\rm d}x \]考虑对上面这个东西分步积分
\[\int_s^{x_0+s}x^n(x+t-s)^m{\rm d}x=[\frac{x^{n+1}}{n+1}(x+t-s)^m]_{s}^{x_0+s}-\int_s^{x_0+s}\frac{x^{n+1}}{n+1}m(x+t-s)^{m-1} \]后面的这个式子可以递归，可以做到\(O(n+m)\)
算法EX
这时候，你想\(A\)掉这道题
#include
#define mod 2147483647
#define int long long
#define MAXN 200002
using namespace std;
int N,s,t,x0;
int pt[MAXN],fac[MAXN],inv[MAXN],invs[MAXN],pows[MAXN],powt[MAXN],spow[MAXN],tpow[MAXN];
int my_pow(int x,int y)
{
int res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y=(y>>1);
}
return res;
}
int Inv(int x)
{
return my_pow(x,mod-2);
}
void Init()
{
fac[0]=1;
for(int i=1;i=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
int tmp=s-t;
tmp+=(tmp>>31)&mod;
for(int i=1;i>31&mod;
}
}
signed main()
{
scanf("%lld %lld %lld %lld",&N,&s,&t,&x0);
Init();
for(int i=1;i*i<=N;++i)
{
int res=(pows[i*i+1]-spow[i*i+1])*invs[i*i+1]%mod;
for(int j=1;j<=N;++j)
{
(res=pows[i*i+1]*powt[j]%mod+pt[j]*(mod-res)%mod)%=mod;
(res+=(mod-spow[i*i+1])*tpow[j])%=mod;
res%=mod;
res+=res>>63&mod;res+=res>>63&mod;
(res*=invs[i*i+j+1])%=mod;
if((int)sqrt(j)*(int)sqrt(j)==j)
cout<<(res%mod+mod)%mod<<" ";
}
cout< \(T2\ math\)
考虑一下单位根的性质
\[\sum_{i=0}^{n-1}w_n^{i\times k}= \left\{ \begin{array}{**lr**} n\ \ \ \ n \mid k \\ 0\ \ \ \ n\nmid k& \end{array} \right. \]有多项式
\[f(x)=a_0+a_1 x+a_2 x^2...+a_K x^K \]把\(x^n=1\)的根\(r\)全部带进去，\(\sum f(r)\)
\[\sum_{i=1}^n f(r_i)=\sum_{i=0}^{n-1}f(w_n^i)=\sum_{i=0}^{n-1}\sum_{j=0}^Ka_jw_n^{ij}=\sum_{j=0}^Ka_j\sum_{i=0}^{n-1}w_n^{ij}=n\times\sum_{j=0}^{\lfloor\frac{K}{n}\rfloor}a_{in} \]我们要求所有的不超过\(n\)次的单位根，重复的只求一次的\(\sum f(r)\)
设本原单位根为\(w_n^k,\gcd(n,k)=1\)
\(F(i)=\sum f(r)[r\)是\(i\)次本原单位根\(]\)
\(G(i)=\sum f(r)[r\)是\(i\)次单位根\(]\)
\[\sum_{d\mid n}F(d)=G(n) \]考虑证明：
我们每个单位根第一次出现肯定在因数的位置，感觉这个东西和\(\sum_{d|n}\varphi(d)=n\)有点像
\[F*I=G \\ F=G/I \]考虑用杜教筛解决
#include
//#define int long long
#define ll long long
#define rint register int
#define LL __int128
#define N 10000010
using namespace std;
char buf[1<<21],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int n,k,a[N],tot;
ll idn[N],IDN[N];
ll ID(ll x)
{
if(x<=n/x) return idn[x]=idn[x]?idn[x]:++tot;
else return IDN[n/x]=IDN[n/x]?IDN[n/x]:++tot;
}
bitset sh;
ll prime[N],phi[N],qzp[N],f[N],mu[N],qzm[N];
int cnt;
ll phis[N],mus[N];
ll Phi(ll x)
{
if(x<=N-10) return qzp[x];
if(phis[ID(x)]) return phis[ID(x)];
ll ans=(x+1)*x/2;
for(ll l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*Phi(x/l);
}
return phis[ID(x)]=ans;
}
int Mu(rint x)
{
if(x<=N-10) return qzm[x];
if(mus[ID(x)]) return mus[ID(x)];
rint ans=1;
for(rint l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*Mu(x/l);
}
return mus[ID(x)]=ans;
}
void write(LL x)
{
if(x/10) write(x/10);
putchar(x%10+'0');
}
inline int read()
{
rint 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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
signed main()
{
n=read(),k=read();
qzp[1]=phi[1]=mu[1]=qzm[1]=1;
for(ll i=2;i<=N-10;++i)
{
if(!sh[i])
{
prime[++cnt]=i;
phi[i]=i-1;
mu[i]=-1;
}
for(rint j=1;j<=cnt&&prime[j]*i \(T3\ viru\)
暴力可以拿\(90pts\)
考虑对于每种颜色，求哪些矩阵不能包含。
考虑如何\(O(n^3)\)
首先根号分治，出现次数小的直接暴力，出现次数大的考虑扫一遍
扫的话，考虑枚举下边界，左右边界，我们需要求的是，每一列最靠下的位置在哪。
可以拿到\(90pts\)(粘一下其他老哥代码)
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include
#include
#include
#include
#include
using namespace std;
const int N=1510;
int n,m,w[N],h[N],up[N][N];
bool a[N][N];stack s;
vector v[N*N];
long long ans;
void calc1(int p){
sort(v[p].begin(),v[p].end());
for(int i=0;i=y)r=min(_y-1,r);
last=_x;
}
ans+=1ll*(n-last)*(r-y+1)*(y-l+1)*(x+1);
}
return;
}
void calc2(int p){
for(int i=0;i 正解的话需要笛卡尔树
#include
#define ls t[x].l
#define rs t[x].r
using namespace std;
struct node{
int fa,l,r,L,R,val,s;
void init()
{
fa=l=r=L=R=val=s=0;
}
}t[2250011];
int n,cnt,sum,rt,la;
int col[2250011],id[2250011],x[2250011],y[2250011];
int exis[2250011],p[2250011],g[2250011];
long long ans;
bool cmp(int a,int b)
{
if(col[a]==col[b]) return ar)return 0;
int mid=(l+r)>>1;
t[mid].fa=f,t[mid].L=p[l-1],t[mid].R=p[r+1];
t[mid].l=build(mid,l,mid-1),t[mid].r=build(mid,mid+1,r);
return mid;
}
void re(int x)
{
int f=t[x].fa,gf=t[f].fa;
if(gf)
{
if(t[gf].l==f) t[gf].l=x;
if(t[gf].r==f) t[gf].r=x;
}
if(t[f].l==x) t[rs].fa=f,t[f].l=rs,rs=f;
else t[ls].fa=f,t[f].r=ls,ls=f;
t[f].fa=x,t[x].fa=gf;
push_up(f);
}
void tar(int x,int c)
{
t[x].val=c;
int f=0;
while(f=t[x].fa)
{
if(t[f].val>=t[x].val) break;
re(x);
}
while(1)
{
push_up(x);
if(!t[x].fa) return rt=x,void();
x=t[x].fa;
}
}
void gets(int l,int r)
{
cnt=sum=0;
for(int i=l;i<=r;++i)
{
cnt++;
x[cnt]=((id[i]-1)/n)+1;
y[cnt]=((id[i]-1)%n)+1;
if(!exis[y[cnt]]) exis[y[cnt]]=1,p[++sum]=y[cnt];
}
p[0]=0,p[sum+1]=n+1;
sort(p+1,p+sum+1);
}
void chu_ans(int l,int r)
{
gets(l,r);
for(int i=1;i<=sum;++i) t[i].init();
for(int i=1;i<=sum;++i) g[p[i]]=i;
rt=build(0,1,sum),la=0;
for(int i=1;i<=cnt;++i)
{
ans=ans+1ll*t[rt].s*(x[i]-1-la);
la=x[i]-1;
tar(g[y[i]],x[i]);
}
ans=ans+1ll*t[rt].s*(n-la);
for(int i=1;i<=sum;++i) exis[p[i]]=0;
}
//char buf[1<<21],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(int i=1;i<=n*n;++i) col[i]=read();
int all_the_same=col[1];
for(int i=1;i<=n*n;++i) if(col[i]!=all_the_same) all_the_same=0;
// cerr<<"ww";
if(all_the_same) cout<<1ll*n*(n+1)*n*(n+1)/4,exit(0);
for(int i=1;i<=n*n;++i) id[i]=i;
sort(id+1,id+n*n+1,cmp);
for(int l=1,r;l<=n*n;l=r+1)
{
r=l;
while(r