2018.8.5 正睿暑期集训营 Day2
时间：4h(实际)
期望得分：100+20+40~60
实际得分：80+20+40=140
总结
A.占领地区(前缀和)
计算覆盖的格子，如果不考虑交叉，单独算主对角线(向右斜的统称主对角线了)与副对角线(所有向左斜的)的话很容易。那先算出这个的答案。
考虑主次对角线交叉的部分，我们枚举每条次对角线，看它与哪些主对角线有交点，这是一个区间，那么好像可以二分。
而如果以x=y这条对角线为边界的话，确实可以二分两次来确定这个区间。
但是交点是指在格点上相交。这相当于两条直线的交点有整数解。但是可以发现每相邻两条副对角线，它们在格点上有交点的主对角线是正好互斥的。
再观察下，然后可以分奇偶性，求前缀和就行了。
但是不需要二分，因为我们可以O(1)计算出区间位置，然后前缀和。
分奇偶性的话前缀和从i-2转移就行了。
把坐标系旋转45°找规律会更方便些。
//19ms 1820kb
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+7;
int n,m,sum[N<<1];
bool vis2[N<<1];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
// freopen("A.in","r",stdin);
n=read(), m=read();
for(int i=1,x,y; i<=m; ++i)
x=read(), y=read(), sum[x+y]=1, vis2[x-y+n]=1;
LL ans=0; int lim=n<<1;
for(int i=2; i<=lim; ++i)//先枚举主对角线好麻烦啊
{
if(sum[i]) ans+=n-std::abs(n-i+1);
sum[i]+=sum[i-2];
}
for(int i=1; i<lim; ++i)
if(vis2[i])
{
ans+=n-std::abs(n-i);
ans-=sum[lim-std::abs(n-i)]-sum[std::abs(n-i)];//2+|n-i|~2n-|n-i|
}
printf("%lld\n",1ll*n*n-ans);
return 0;
}
B.配对(组合)
\(Solution\)
有一个只有一条边有权值的部分分，对于某种位置分布情况，我们肯定是在这条边两侧尽量配对。
这样扩展到每一条边，如果它两边能配对，我们应尽量让两边的配对，多走这条边的路，即\(dis\)一定会增加。
那么我们可以对每一条边计算其贡献。\(O(m^2)\)枚举它一边男女生人数就可以得到所有情况。设它某一边连通块点数为\(x\)，则边\(now\)的贡献为：$$w_{now}\times\sum_{i=0}m\sum_{j=1}m(\min(i,m-j)+\min(m-i,j))C_miC_mjxi(n-x){m-j}xj(n-x){m-i}$$
把前面只与\(i,j\)有关的放到前面，枚举边：$$\sum_{i=0}m\sum_{j=0}m(\min(i,m-j)+\min(m-i,j))C_miC_mj\sum_{edge}w_{edge}x{i+j}(n-x){2m-(i+j)}$$
这样就只与\(i+j\)有关了，预处理所有边在\(i+j\)的贡献。复杂度\(O(nm)\)。
还有对min进行处理的容斥方法，不管了。
为什么跑7000+ms。。哪看都没有问题。。组合数啥的都是O(m)的啊
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod (1000000007)
typedef long long LL;
const int N=2504,M=N<<1;
int n,m,Enum,H[N],nxt[M],to[M],len[M],sz[N],X[M],val[M],inv[N],C[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int w,int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], len[Enum]=w, H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], len[Enum]=w, H[v]=Enum;
}
inline LL FP(LL x,int k)
{
LL t=1;
for(; k; k>>=1, x=x*x%mod)
if(k&1) t=t*x%mod;
return t;
}
void DFS(int x,int f)
{
sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=f)
{
DFS(v,x), sz[x]+=sz[v];
X[i]=X[i^1]=sz[v];
}
}
int main()
{
n=read(), m=read(), Enum=1;
for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
DFS(1,1);
for(int i=0,lim=m<<1; i<=lim; ++i)
{
LL tmp=0;
for(int j=1; j<=Enum; j+=2)
tmp+=1ll*len[j]*FP(X[j],i)%mod*FP(n-X[j],lim-i)%mod;
val[i]=(int)(tmp%mod);
}
C[0]=inv[1]=1;
for(int i=2; i<=m; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1; i<=m; ++i) C[i]=1ll*C[i-1]*(m-i+1)%mod*inv[i]%mod;
LL ans=0;
for(int i=0; i<=m; ++i)
for(int j=0; j<=m; ++j)
ans+=1ll*(std::min(i,m-j)+std::min(m-i,j))*C[i]%mod*C[j]%mod*val[i+j]%mod;
printf("%lld\n",ans%mod);
return 0;
}
C 导数卷积(NTT)
先令\(n-1\)。
\[g(x)=\sum_{i=0}^nf^{(i)}(x)f^{(n-i)}(x)
\]
\]
肯定不能是\(n\)次卷积求。。我们尝试直接一次求出\(g(x)\)的各项系数。
用\(G_i\)表示\(g(x)\)的\(x^i\)的系数，\(F_i\)表示\(f(x)\)的\(x^i\)的系数。
首先\(f(x)\)经过\(i\)次求导后，\(x^j\)的系数为\(F_{i+j}\frac{(i+j)!}{j!}\)。
则$$G_d=\sum_{i=0}d\sum_{j=0}nF_{i+j}\frac{(i+j)!}{i!}F_{n-j+d-i}\frac{(n-j+d-i)!}{(d-i)!}$$（先枚举左边多项式的\(x\)的次数\(i\)，再枚举它是经过\(j\)次求导后的，然后确定右边多项式的系数）
令\(F(i)=F(i)\times i!\)，则$$G_d=\sum_{i=0}d\sum_{j=0}nF_{i+j}F_{n-j+d-i}\frac{1}{i!(d-i)!}$$
两个\(F()\)都有\(i+j\)，为了不动后面的\(i\)，令\(j=i+j\)，则$$G_d=\sum_{j=0}{n+d}F_jF_{n+d-j}\sum_{i=0}d\frac{1}{i!(d-i)!}\times[i\leq j]\times[d-i\leq n+d-j]$$（\(i\)的枚举当然和\(j\)有关系啊。这里只要满足前面阶乘中的 \(i\leq i+j\) 和 \(d-i\leq n+d-(i+j)\) 就可以了）
后面小于等于的限制比较烦人。可以发现，当 \(j<d\) 时，\(n+d-j>n\)，而\(F\)只有\(F_{0,\cdots,n}\)不为\(0\)，即\(F_{n+d-j}=0\)，可以忽略\([i\leq j]\)。
同理，\(n+d-j<d\) 时，\(F_j=0\)，后一项也可以忽略。
所以有$$G_d=\sum_{j=0}{n+d}F_jF_{n+d-j}\sum_{i=0}d\frac{1}{i!(d-i)!}$$
其中$$\sum_{i=0}d\frac{1}{i!(d-i)!}=\frac{2d}{d!}$$
NTT，然后乘上后面那个求和就行了。
//311ms 7632kb
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define G (3)
#define inv_G (332748118)
#define mod (998244353)
typedef long long LL;
const int N=(1<<18)+5;
int n,rev[N];
LL fac[N],inv[N],F[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline LL read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline LL FP(LL x,int k)
{
LL t=1;
for(; k; k>>=1, x=x*x%mod)
if(k&1) t=t*x%mod;
return t;
}
void NTT(LL *a,int lim,int type)
{
for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
for(int i=2; i<=lim; i<<=1)
{
int mid=i>>1;
LL Wn=FP(~type?G:inv_G,(mod-1)/i);
for(int j=0; j<lim; j+=i)
{
LL w=1,t;
for(int k=0; k<mid; ++k,w=w*Wn%mod)
a[j+k+mid]=(a[j+k]-(t=w*a[j+k+mid]%mod)+mod)%mod,
// a[j+k+mid]=a[j+k]-(t=w*a[j+k+mid]%mod), a[j+k+mid]<0&&(a[j+k+mid]+=mod),
a[j+k]+=t, a[j+k]>=mod&&(a[j+k]-=mod);
}
}
if(type==-1) for(int i=0,inv=FP(lim,mod-2); i<lim; ++i) a[i]=a[i]*inv%mod;
}
int main()
{
n=read()-1, fac[0]=1;
for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*i%mod;
inv[n]=FP(fac[n],mod-2);
for(int i=n-1; ~i; --i) inv[i]=inv[i+1]*(i+1)%mod;
for(int i=0; i<=n; ++i) F[i]=read()*fac[i]%mod;
int l=-1, lim=1;
while(lim<=n<<1) ++l, lim<<=1;
for(int i=1; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
NTT(F,lim,1);
for(int i=0; i<lim; ++i) F[i]=F[i]*F[i]%mod;
NTT(F,lim,-1);
for(int i=n,pw2=1; i<=(n<<1); ++i) printf("%d ",(int)(F[i]*pw2%mod*inv[i-n]%mod)), pw2<<=1, pw2>=mod&&(pw2-=mod);
return 0;
}
考试代码
T1
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+7;
int n,m,cnt,val[N],X[N],Y[N],sum1[N],sum2[N];
bool vis1[N<<2],vis2[N<<2],vis3[N<<2];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Spec
{
bool vis[3003][3003];
void Main()
{
int ans=0;
for(int i=1,x,y; i<=n; ++i)
{
x=read(), y=read();
if(x+y<=m+1)
{
for(int x0=x+y-1,y0=1; x0&&y0<=m; --x0,++y0)
if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;
}
else
{
for(int x0=m,y0=x+y-m; x0&&y0<=m; --x0,++y0)
if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;
}
if(x-y<=0)
{
for(int x0=1,y0=1-x+y; x0<=m&&y0<=m; ++x0,++y0)
if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;
}
else
{
for(int x0=x-y+1,y0=1; x0<=m&&y0<=m; ++x0,++y0)
if(!vis[x0][y0]) ++ans, vis[x0][y0]=1;
}
}
printf("%d\n",m*m-ans);
}
}
inline bool Check()
{
for(int i=1; i<=n; ++i) if(X[i]+Y[i]==m+1) return 1;
return 0;
}
int QueryL(int v,int r)
{
// if(v==m+1) return 1;
int l=1,mid,ans=r;
while(l<=r)
{
mid=l+r>>1;
if((v<m+1&&v-1>=1-val[mid])||(v>m+1&&v-m<=val[mid]+m)) ans=mid, r=mid-1;//cross
else l=mid+1;
}
return ans;
}
int QueryR(int v,int l)
{
// if(v==m+1) return cnt;
int r=cnt,mid,ans=l;
while(l<=r)
{
mid=l+r>>1;
if((v<m+1&&v-1>=val[mid]+1)||(v>m+1&&v-m<=m-val[mid])) ans=mid, l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
// freopen("A.in","r",stdin);
m=read(), cnt=n=read();
// if(n<=3000&&m<=3000) {Spec::Main(); return 0;}
bool f=0; LL Ans=0;
for(int i=1; i<=n; ++i)
{
X[i]=read(), Y[i]=read(), val[i]=X[i]-Y[i];
if(!val[i]) f=1;
if(!vis1[X[i]-Y[i]+m]) Ans+=m-std::abs(X[i]-Y[i]), vis1[X[i]-Y[i]+m]=1;
if(!vis2[X[i]+Y[i]]) Ans+=m-std::abs(X[i]+Y[i]-m-1), vis2[X[i]+Y[i]]=1;
}
if(!f) val[++cnt]=0;
std::sort(val+1,val+1+cnt); int c=1;
for(int i=2; i<=cnt; ++i)
if(val[i]!=val[i-1]) val[++c]=val[i];
cnt=c;
int p=1;
for(int i=2; i<=cnt; ++i) if(!val[i]) {p=i; break;}
int t=0;
if(Check())//exist i:xi+yi==m+1
{
for(int i=1; i<=cnt; ++i) if(!((m+1+val[i])&1)) ++t;
vis3[m+1]=1, Ans-=t;
}
for(int i=1; i<=cnt; ++i)
sum1[i]=sum1[i-1]+(val[i]&1), sum2[i]=sum2[i-1]+((val[i]&1)^1);
t=0;
for(int i=1,s,L,R; i<=n; ++i)
{
if(vis3[s=X[i]+Y[i]]) continue;
vis3[s]=1, t+=(s&1)^1;//WA：不一定与主对角线相交！
R=QueryR(s,p), L=QueryL(s,p);
if(s&1) Ans-=sum1[R]-sum1[L-1];
else Ans-=sum2[R]-sum2[L-1];
}
if(!f) Ans+=t;
printf("%lld\n",1ll*m*m-Ans);
return 0;
}
T2
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod (1000000007)
typedef long long LL;
const int N=2505;
int n,m,Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],pos[N<<1],fa[N],dep[N];
LL Ans,dis[N];
bool match[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int w,int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void T_DFS(int x)
{
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
fa[v]=x, dep[v]=dep[x]+1, dis[v]=dis[x]+len[i], T_DFS(v);
}
inline int LCA(int u,int v)
{
while(u!=v) dep[u]>dep[v]?u=fa[u]:v=fa[v];
return u;
}
inline LL Dis(int x,int y){
return dis[x]+dis[y]-(dis[LCA(x,y)]<<1);
}
void DFS2(int x,LL now,LL &mx)
{
if(x>m)
{
mx=std::max(mx,now);
return;
}
for(int i=1; i<=m; ++i)
if(!match[i]) match[i]=1, DFS2(x+1,now+Dis(pos[x],pos[i+m]),mx), match[i]=0;
}
void Calc()
{
LL mx=0;
DFS2(1,0,mx);
Ans+=mx%mod, Ans>=mod&&(Ans-=mod);
}
void DFS(int x)
{
if(x>m<<1) {Calc(); return;}
for(int i=1; i<=n; ++i) pos[x]=i, DFS(x+1);
}
int main()
{
// freopen(".in","r",stdin);
n=read(), m=read();
for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
T_DFS(1), DFS(1);
printf("%lld\n",Ans%mod);
return 0;
}
T3
早就忘了NTT怎么写。。
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define G (3)
#define inv_G (332748118)
#define mod (998244353)
typedef long long LL;
const int N=5003,M=8300;
int n,A[N][M],B[M],C[M],len[N],rev[M];
LL g[N],inv_lim;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline LL FP(LL x,int k)
{
LL t=1;
for(; k; k>>=1, x=x*x%mod)
if(k&1) t=t*x%mod;
return t;
}
void NTT(int *a,int lim,int type)
{
for(int i=1; i<lim; ++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
for(int i=2; i<=lim; i<<=1)
{
int mid=i>>1;
LL Wn=FP(~type?G:inv_G,(mod-1)/i),t,w;
for(int j=0; j<lim; j+=i)
{
LL w=1;
for(int k=0; k<mid; ++k, w=w*Wn%mod)
a[j+k+mid]=(a[j+k]-(t=w*a[j+k+mid]%mod)+mod)%mod,
a[j+k]=(a[j+k]+t)%mod;
}
}
if(type==-1) for(int i=0; i<lim; ++i) a[i]=1ll*a[i]*inv_lim%mod;
}
void P_Mul(int *b,int *c,int l1,int l2)
{
int L=-1, lim=1;
while(lim<=l1+l2) lim<<=1, ++L;
inv_lim=FP(lim,mod-2);
for(int i=1; i<lim; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
for(int i=0; i<lim; ++i) B[i]=b[i], C[i]=c[i];
NTT(B,lim,1), NTT(C,lim,1);
for(int i=0; i<lim; ++i) B[i]=1ll*B[i]*C[i]%mod;
NTT(B,lim,-1);
}
int main()
{
// freopen("C.in","r",stdin);
// freopen("my.out","w",stdout);
n=read()-1;
for(int i=0; i<=n; ++i) A[0][i]=read();
len[0]=n+1;
for(int x=1; x<=n; ++x)
{
int *a=A[x], *b=A[x-1]; len[x]=n-x+1;
for(int i=0,lim=n-x; i<=lim; ++i) a[i]=1ll*(i+1)*b[i+1]%mod;
}
for(int i=0,lim=(n+1)>>1; i<lim; ++i)
{
P_Mul(A[i],A[n-i],len[i],len[n-i]);
for(int i=0; i<=n; ++i) g[i]+=B[i]<<1;
}
if(!(n&1))
{
P_Mul(A[n>>1],A[n>>1],len[n>>1],len[n>>1]);
for(int i=0; i<=n; ++i) g[i]+=B[i];
}
for(int i=0; i<=n; ++i) printf("%d ",(int)(g[i]%mod));
return 0;
}