A Social Distancing

在半径为$r$的圆内的格点中放入$n$个点.
使得两两距离的平方之和最大.
$n\le 8,r\le 30$.

一开始想到搜索但是点数过多了.
我们来考虑推式子优化:
${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}d(i,j)={\sum }_{i=1}^n{\sum }_{j=i+1}^n{x}_i^2+y_i^2+x_j^2+y_j^2-2x_i{x}_j-2y_i{y}_j=n({\sum }_{i=1}^n{x}_i^2+y_i^2)-(\sum x_i{)}^2-(\sum y_i{)}^2$

考虑dp,$f[i][j][k]$表示选$i$个点,$\sum x=j$,$\sum y=k$.
然后 a n s [ i ] [ r ] = max ⁡ { n ∗ f [ i ] [ j ] [ k ] − j 2 − k 2 } ans[i][r]=\max\{n*f[i][j][k]-j^2 -k^2\} ans[i][r]=max{n∗f[i][j][k]−j2−k2}
这样做肯定会T的–打表就好.

打表程序:

#include<bits/stdc++.h>
#define x first
#define y second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator 
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20,mod=998244353,inf=2e9;//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {char c=gc; x=0; int f=1;while(!isdigit(c)){if(c=='-')f=-1; c=gc;}while(isdigit(c)) x=x*10+c-'0',c=gc;x*=f;
}
template<class o> void qw(o x) {if(x/10) qw(x/10);putchar(x%10+'0');
}
template<class o> void pr1(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar(' ');
}
template<class o> void pr2(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar('\n');
}int T,n,r,f[10][610][610],ans[11][33];
vector<pii> s;
const int base=303;void upd(int &x,int y) {x=max(x,y);}int main() {r=30;for(int i=-r;i<=r;i++)for(int j=-r;j<=r;j++)if(i*i+j*j<=r*r) s.pb(mk(i,j));memset(f,-2,sizeof f);f[0][base][base]=0;puts("{");for(r=1;r<=30;r++) {for(auto it:s) if(it.x*it.x+it.y*it.y<=r*r)for(int i=0;i<8;i++)for(int j=base-r*i;j<=base+r*i;j++)for(int k=base-r*i;k<=base+r*i;k++) if(f[i][j][k]>=0) upd(f[i+1][j+it.x][k+it.y],f[i][j][k]+it.x*it.x+it.y*it.y);for(int i=1;i<=8;i++)for(int j=base-r*i;j<=base+r*i;j++)for(int k=base-r*i;k<=base+r*i;k++) if(f[i][j][k]>=0) ans[i][r]=max(ans[i][r],(i*f[i][j][k]-(j-base)*(j-base)-(k-base)*(k-base)));printf("\t{");for(int i=1;i<=8;i++) printf("%d,",ans[i][r]);puts("},");}puts("};");
}

AC代码:

#include<bits/stdc++.h>
using namespace std;void qr(int &x) {scanf("%d",&x);}int T,n,r;int ans[][11]= {{0},{0,4,8,16,24,36,48,64,},{0,16,32,64,96,144,192,256,},{0,36,76,144,218,324,432,576,},{0,64,130,256,384,576,768,1024,},{0,100,224,400,624,900,1224,1600,},{0,144,312,576,880,1296,1740,2304,},{0,196,416,784,1188,1764,2356,3136,},{0,256,554,1024,1572,2304,3102,4096,},{0,324,722,1296,2014,2916,3954,5184,},{0,400,896,1600,2496,3600,4896,6400,},{0,484,1064,1936,2984,4356,5872,7744,},{0,576,1248,2304,3520,5184,6960,9216,},{0,676,1512,2704,4224,6084,8280,10816,},{0,784,1746,3136,4870,7056,9564,12544,},{0,900,2016,3600,5616,8100,11016,14400,},{0,1024,2264,4096,6336,9216,12456,16384,},{0,1156,2600,4624,7224,10404,14160,18496,},{0,1296,2888,5184,8056,11664,15816,20736,},{0,1444,3218,5776,9008,12996,17666,23104,},{0,1600,3584,6400,9984,14400,19584,25600,},{0,1764,3912,7056,10942,15876,21500,28224,},{0,1936,4344,7744,12080,17424,23688,30976,},{0,2116,4712,8464,13144,19044,25808,33856,},{0,2304,5138,9216,14326,20736,28122,36864,},{0,2500,5612,10000,15624,22500,30624,40000,},{0,2704,6062,10816,16896,24336,33120,43264,},{0,2916,6536,11664,18184,26244,35664,46656,},{0,3136,6984,12544,19488,28224,38266,50176,},{0,3364,7520,13456,20968,30276,41200,53824,},{0,3600,8084,14400,22480,32400,44076,57600,},
};int main() {qr(T); while(T--) qr(n),qr(r),printf("%d\n",ans[r][n-1]);
}

B Mask Allocation

$n\ast m$ 个口罩,分成若干个单元,同时满足 能分成和为 $n$的$m$组 还有 和为$m$的$n$组.
求最小化单元数的情况下字典序最大的方案.
$n,m\le 1e4$.

设求解函数为$f(n,m)$.
令$n\le m$.
那么要最小化单元数 就必须每个单元都尽量的大.
明显每个单元$\le n$.

那么对于第二种情况,$n$组,每组$m$个.
$m$个用$n$来覆盖,那么剩余$n$组,每组$m\mathrm{m}\mathrm{o}\mathrm{d}n$.

对于第一种情况,剩余$m\mathrm{m}\mathrm{o}\mathrm{d}n$组,每组$n$个.

发现 组 和 总和 是互换关系,即$f(m\mathrm{m}\mathrm{o}\mathrm{d}n,n)$.

复杂度为$O(\log n+\log m)$(不计输出)

int T,n,m;int main() {qr(T); while(T--) {qr(n); qr(m);vector<int> ans;while(1) {if(n>m) swap(n,m);if(!n) break;int i=m/n*n;while(i--) ans.pb(n);m %= n;}pr2(SZ(ans));for(int i:ans) pr1(i);puts("");}
}

C A National Pandemic

初始$\forall i,f(i)=0$.
你需要执行3类操作:

1. 有两个参数$x,w$,$\forall y,f(y)+=w-dis(x,y)$.
2. 参数为$x$,$f(x)=\min (f(x),0)$.
3. 参数为$x$,询问$f(x)$.

主要难处理的是第一项:
我们的突破口是 $dis(x,y)$.
$\Delta =w-dis(x,y)=w-(dep[x]+dep[y]-2dep[lca(x,y)])$
我们可以全局记录一个$\Delta =w-dep[x]$.
然后我们把$x$到根的路径每个点都+2.(表示+2dep[lca(x,y)]).
我们记录一下前面的操作一次数$t$,那么询问的时候加上$t\ast dep[y]$,
然后询问$y$到根的路径和.(两条路径的公共部分就是$dep[lca]$)

总复杂度为$O(m{\log }^{2}n)$.

听说可以用点分树,但是不会.

#include<bits/stdc++.h>
#define x first
#define y second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator 
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=5e4+10,size=1<<20,mod=998244353,inf=2e9;//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {char c=gc; x=0; int f=1;while(!isdigit(c)){if(c=='-')f=-1; c=gc;}while(isdigit(c)) x=x*10+c-'0',c=gc;x*=f;
}
template<class o> void qw(o x) {if(x/10) qw(x/10);putchar(x%10+'0');
}
template<class o> void pr1(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar(' ');
}
template<class o> void pr2(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar('\n');
}int T,n,m,fa[N],dep[N],son[N],sz[N];
struct edge{int y,next; } a[N*2]; int len,last[N];
void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len; }void dfs(int x) {sz[x]=1; son[x]=0;for(int k=last[x],y;k;k=a[k].next) if((y=a[k].y)^fa[x]) {fa[y]=x;dep[y]=dep[x]+1;dfs(y);sz[x] += sz[y];if(sz[son[x]]<sz[y]) son[x]=y;}
}int top[N],dfn[N],id;
void DFS(int x,int tp) {top[x]=tp; dfn[x]=++id;if(son[x]) DFS(son[x],tp);else return ;for(int k=last[x],y;k;k=a[k].next) {y=a[k].y;if(y^fa[x]&&y^son[x]) DFS(y,y);}
}ll c1[N],c2[N];
void add(int x,int d) {for(ll z=x*d;x<=n;x+=x&-x) c1[x]+=d,c2[x]+=z;}
void add(int x,int y,int d) {add(x,d); add(y+1,-d);}ll ask(int x) {ll y=0,z=x+1;for( ;x; x-=x&-x) y+=c1[x]*z-c2[x];return y;
}
ll ask(int l,int r) {return ask(r)-ask(l-1); }void ADD(int x) {while(x) {add(dfn[top[x]],dfn[x],2);x=fa[top[x]];}
}ll ASK(int x) {ll y=0;while(x) y+=ask(dfn[top[x]],dfn[x]),x=fa[top[x]];return y;
}int ts;
ll delta,s[N];
ll F(int x) {return delta+s[x]-1ll*ts*dep[x]+ASK(x);
}int main() {qr(T); while(T--) {qr(n); qr(m); delta=ts=len=id=0; for(int i=1;i<=n;i++) last[i]=fa[i]=c1[i]=c2[i]=s[i]=0;for(int i=1,x,y;i<n;i++) qr(x),qr(y),ins(x,y),ins(y,x);dep[1]=1; dfs(1); DFS(1,1);while(m--) {int op,x,w; qr(op); qr(x);if(op==1) qr(w),++ts,delta+=w-dep[x],ADD(x);else if(op == 2) {ll t=F(x);if(t>0) s[x] -= t;}else pr2(F(x));}}return 0;
}

D Fake News

做法1:
特判$n=1||n=24$
做法2:
容易得到$\frac{n(n+1)(2n+1)}{6}=y^2$.
同时$n,n+1,2n+1$两两互质,所以我们只要把6在他们中间除去后判定一下是否为完全平方数即可.

int T;
ll n,a,b,c;
bool pd(ll x) {ll y=sqrt(x+1);return y*y == x;
}
ll gcd(ll x,ll y) {return !x?y:gcd(y%x,x);}int main() {qr(T); while(T--) {qr(n);a=n; b=n+1; c=2*n+1;a/=gcd(a,6);b/=gcd(b,6);c/=gcd(c,6);if(pd(a)&&pd(b)&&pd(c)) puts("Fake news!");else puts("Nobody knows it better than me!");}return 0;
}

G Topo Counting

给定一个烤肉架图.求出其拓扑序的方案数.
$n\le 3000$.

我们把上面$2n$个点当做架子,下面的$(n-1)\ast 2n$个点当做肉片.
这个例图有点问题,就是每块肉少了2个点.

首先,有一个重要结论就是两个互不相关的子图$A,B$,拓扑序分别有$c,d$个.
那么合并两个子图,总拓扑序的方案数为$c\ast d\ast C_{|V(A)|+|V(B)|}^{|V(B)|}$ .

然后如果肉和架子不连通的话方案数就很好求.
但是有这些边,所以我们就必须围绕架子的点的删除情况来考虑肉的联通,当一块肉掉下时,我们就按上面的结论求出答案.

考虑如何删除点:
无论何时,第一行都可以顺序删点.(删除即表示加入拓扑序)
当第一行剩余$<$第二行剩余,我们可以删除第二行第首项.
同时我们还可以删除下面肉的连续若干个.
上面的讨论即所有转移要围绕的条件.

定义$f[i][j]$表示第一行剩余$i$个,第二行剩余$j$个 加上其附属的肉片的总方案数.
$g[i][j]$表示第一二行剩余$i$,然后下面的肉剩余$j$个的方案数.
$($当一块肉分离出来的时候第一列剩余$x$个,第二列剩余$n$个,我们就要求一个卡特兰数$Ca{t}_{x,n}=\left(\genfrac{}{}{0ex}{}{x+n}{x}\right)-\left(\genfrac{}{}{0ex}{}{x+n}{x-1}\right))$(剩余1的个数$\ge$剩余2的个数,可以做一个把转移路径对$y=x-1$做一个对称)

可以得出以下转移:
$f[i][j]=f[i-1][j]$.
$f[i][j]+=g[j][n](j=i+1)$.
$f[i][j]+=f[i][j-1]\ast Ca{t}_n\ast C_{i+j-1+(j-1)\ast 2n}^{2n}$.
$g[i][j]=g[i][j-1]+Ca{t}_{j,n}\ast f_{i-1,i-1}\ast C_{2\ast i-2+(i-2\ast 2n+2n-j}^{2n-j}$.

总复杂度为$O(n^2)$.

#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=3010,size=1<<20,inf=2e9;//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {char c=gc; x=0; int f=1;while(!isdigit(c)){if(c=='-')f=-1; c=gc;}while(isdigit(c)) x=x*10+c-'0',c=gc;x*=f;
}
template<class o> void qw(o x) {if(x/10) qw(x/10);putchar(x%10+'0');
}
template<class o> void pr1(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar(' ');
}
template<class o> void pr2(o x) {if(x<0)x=-x,putchar('-');qw(x); putchar('\n');
}int n,mod,f[N][N],g[N][N];
ll jc[2*N*N],inv[2*N*N];ll power(ll a,ll b=mod-2) {ll c=1;while(b) {if(b&1) c=c*a%mod;b /= 2; a=a*a%mod;}return c;
}
ll C(int x,int y) {if(x<0 || y<0) return 0;return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
ll Cat(int x,int y) {return (C(x+y,x)-C(x+y,x-1)+mod)%mod;}
void ad(int &x,int y) {x += y; x -= (x>=mod)*mod; }int main() {qr(n); qr(mod); jc[0]=1; int m=2*n*n;for(int i=1;i<=m;i++) jc[i]=jc[i-1]*i%mod;inv[m]=power(jc[m]); for(int i=m;i>=0;i--) inv[i-1]=inv[i]*i%mod;f[0][1]=1; //f[i][j]表示第一行剩余i个,第二行剩余j个加上其附属的肉片的总方案数 for(int j=2;j<=n;j++) f[0][j]=(f[0][j-1]*Cat(n,n)%mod*C(j-1+2*(j-1)*n,2*n)%mod);for(int i=1;i<=n;i++) {for(int j=0;j<=n;j++) g[i+1][j]=((j?g[i+1][j-1]:0)+Cat(j,n)*f[i-1][i]%mod*C(2*i-1+(i-1)*2*n+n+j,n+j))%mod;for(int j=i;j<=n;j++) {f[i][j]=f[i-1][j];if(i + 1 == j) ad(f[i][j],g[j][n]);else if(i + 1 < j) ad(f[i][j],(ll)f[i][j-1]*Cat(n,n)%mod*C(i+j-1+(j-1)*2*n,2*n)%mod);}}pr2(f[n][n]); return 0;
}

可以发现这个$g$可以去掉:

int n,mod,f[N][N],jc[2*N*N],inv[2*N*N];ll power(ll a,ll b=mod-2) {ll c=1;while(b) {if(b&1) c=c*a%mod;b /= 2; a=a*a%mod;}return c;
}
ll C(int x,int y) {if(x<0 || y<0) return 0;return (ll)jc[x]*inv[y]%mod*inv[x-y]%mod;
}
ll Cat(int x,int y) {return (C(x+y,x)-C(x+y,x-1)+mod)%mod;}
void ad(int &x,int y) {x += y; x -= (x>=mod)*mod; }int main() {qr(n); qr(mod); jc[0]=1; int m=2*n*n;for(int i=1;i<=m;i++) jc[i]=(ll)jc[i-1]*i%mod;inv[m]=power(jc[m]); for(int i=m;i>=0;i--) inv[i-1]=(ll)inv[i]*i%mod;f[0][1]=1; //f[i][j]±íʾµÚÒ»ÐÐÊ£Óài¸ö,µÚ¶þÐÐÊ£Óàj¸ö¼ÓÉÏÆ丽ÊôµÄÈâƬµÄ×Ü·½°¸Êý for(int j=2;j<=n;j++) f[0][j]=(f[0][j-1]*Cat(n,n)%mod*C(j-1+2*(j-1)*n,2*n)%mod);for(int i=1;i<=n;i++) {for(int j=i;j<=n;j++) {f[i][j]=f[i-1][j];if(i + 1 == j) {ll s=0;for(int j=0;j<=n;j++) s += Cat(j,n)*C(2*i-1+(i-1)*2*n+n+j,n+j)%mod;f[i][j]=(f[i][j]+s%mod*f[i-1][i])%mod;}else if(i + 1 < j) ad(f[i][j],(ll)f[i][j-1]*Cat(n,n)%mod*C(i+j-1+(j-1)*2*n,2*n)%mod);}}pr2(f[n][n]); return 0;
}

H Dividing

神奇的数对定义如下:
1-$(1,k)$.
2-$(n,k)$如果是那么$(nk,k)$也是
3-$(n,k)$如果是那么$(n+k,k)$也是.
求$1\le n\le N,1\le k\le K$的方案数

可以发现每次$k$都不会变化,所以我们可以考虑每一个$k$的答案.
容易发现有两种情况:
$1,1+k,2+k.....$,
$k,2k,3k....$.
分类讨论,然后整除分块做即可.

int T;
ll n,k;ll calc(ll m) {ll s=0;for(ll l=1,r;l<=k&&l<=m;l=++r) {ll x=m/l; r=min(m/x,k);s+=(r-l+1)%mod*(x%mod)%mod;}return s%mod;
}int main() {qr(n),qr(k),pr2((calc(n)+calc(n-1)+(k-1)-(n-1)%mod+mod)%mod);return 0;
}

I Valuable Forests

定义一个森林/树的$val$为所有点度数的平方和.
求$n$个点的所有森林/树的$val$总和.
$n\le 5000$.

首先,我们考虑求大小为$n$的树的$val$总和(设为$va{l}_n$).
根据$prufer$编码,一颗无根树有$t{r}_n=n^{n-2}$种情况.
如果一个点的度数为$d$,那么在$prufer$中这个点会出现$d-1$次.
则有转移: $va{l}_i={\sum }_{j=1}^i{j}^2\ast \left(\genfrac{}{}{0ex}{}{i-2}{j-1}\right)\ast (i-1{)}^{(i-2)-(j-1)}$.

然后我们设$f_n,g_n$分别表示大小为$n$的森林的方案数和$val$总和.
考虑$n$和多少个点($d$)形成一棵树,得到转移:
$f_n={\sum }_{d=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)\ast t{r}_{d+1}\ast f_{i-1-d}$,
$g_n={\sum }_{d=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)\ast \left(f_{n-1-d}\ast va{l}_{d+1}+t{r}_{d+1}\ast g_{n-1-d}\right)$(即互相贡献)

总复杂度为$O(n^2)$.

int T,mod,n,C[N][N];
ll p[N],val[N],tr[N],f[N],g[N];ll power(ll a,ll b) {ll c=1;while(b) {if(b&1) c=c*a%mod;b /= 2; a=a*a%mod;}return c;
}int main() {qr(T); qr(mod); C[0][0]=1; n=5000;for(int i=1;i<=n;i++) {C[i][0]=1;for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}tr[1]=1; p[0]=1; f[0]=f[1]=1;for(int i=2;i<=n;i++) {tr[i]=power(i,i-2);for(int j=1;j<=i-2;j++) p[j]=p[j-1]*(i-1)%mod;for(int j=1;j<i;j++) val[i] += (ll)j*j*C[i-2][j-1]%mod*p[(i-2)-(j-1)]%mod;val[i] = val[i]%mod*i%mod;//大小为i的树的val总和for(int j=0;j<i;j++) f[i]=(f[i]+C[i-1][j]*tr[j+1]%mod*f[i-1-j])%mod,g[i]=(g[i]+C[i-1][j]*(tr[j+1]*g[i-1-j]%mod+f[i-1-j]*val[j+1]%mod)%mod)%mod;}while(T--) qr(n),pr2(g[n]);return 0;
}

J Pointer Analysis

指针分析.

需要注意 $a\sim z$ 是对象,$a.\ast ,A,A.\ast$都是指针.
我们对每一个指针记录其可指向的对象,可以考虑状压指向的对象.

char l[210][5],r[210][5];
int n,f[N*N],id[150],tot,s;int main() {for(int i='a';i<='z';i++) id[i]=tot,tot+=26;for(int i='A';i<='Z';i++) id[i]=tot++;qr(n); for(int i=1;i<=n;i++) scanf("%s = %s",l[i],r[i]);while(1) {for(int i=1;i<=n;i++) {int a=id[l[i][0]],b=id[r[i][0]];if(islower(r[i][0])) f[a] |= 1<<(r[i][0]-'a');else {if(!l[i][1]) {if(!r[i][1]) f[a] |= f[b];else {for(int j=0;j<26;j++)if(f[b]>>j&1) f[a] |= f[id[j+'a']+r[i][2]-'a'];}}else {for(int j=0;j<26;j++)if(f[a]>>j&1) f[id[j+'a']+l[i][2]-'a'] |= f[b];}}}int last=s; s=0;for(int i=0;i<tot;i++) s += f[i];if(last==s) break;}for(int i='A';i<='Z';i++) {printf("%c: ",i);for(int j=0;j<26;j++)if(f[id[i]]>>j&1) putchar(j+'a');puts("");}
}