构造
递推构造+矩阵加速
矩阵乘法有介绍。
P3990
- 朴素\(dp\)
复杂度\(O(nm^2)\)
2.小优化\(dp\)
注意到 $$ f[i][j-2]= \left{ \begin{array}{ll} f[i+1][j-3]+...\f[i][j-3]+...\f[i-1][j-3]+... \end{array} \right . $$
因此
注意特判，因为只有\(j\geq 4\)时才有\(f[i][j-3]...\)这些项，才需要加上\(f[i][j-2]\),不然会重复。如\(f[1][3]\)只会加上\(f[1][1]\)这个初始值，而\(f[1][1]\)不是递推得来的。
复杂度\(O(nm)\)
- 矩阵加速
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=110,P=30011;
int n,m;
int g[N][N];
struct ma{
int f[N][N],n,m;
ma(){
memset(f,0,sizeof f),n=m=0;
}
}s,t,ans;
ma operator *(ma a,ma b){
ma c=ma();
int x=a.n,y=a.m,z=b.m;
c.n=x,c.m=z;
for(int i=0;i<x;++i)
for(int j=0;j<z;++j)
for(int k=0;k<y;++k) c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j]%P)%P;
return c;
}
ma kp(ma x,int p){
if(p<=1) return x;
if(p&1) return x*kp(x*x,p>>1);
else return kp(x*x,p>>1);
}
void init(){
t.n=t.m=n+n;
for(int i=0;i<n;++i){
int l=max(0ll,i-1),r=min(n-1,i+1);
for(int j=l;j<=r;++j) t.f[i][j]=1;
t.f[i][n+i]=t.f[n+i][i]=1;
}
memset(g,0,sizeof g);
g[1][1]=1;
for(int j=2;j<=3;++j){
for(int i=1;i<=n;++i){
if(i+1<=n) g[i][j]+=g[i+1][j-1];
if(i-1>=1) g[i][j]+=g[i-1][j-1];
g[i][j]+=g[i][j-1];
if(j-3>=1) g[i][j]+=g[i][j-2];
}
}
s.n=n+n,s.m=1;
for(int i=0;i<n;++i) s.f[i][0]=g[i+1][3];
for(int i=n;i<n+n;++i) s.f[i][0]=g[i-n+1][2];
}
signed main(){
scanf("%lld%lld",&n,&m);
init();
if(m<=3){
printf("%lld",g[n][m]%P);
}else{
ans=kp(t,m-3)*s;
printf("%lld",ans.f[n-1][0]%P);
}
return 0;
}
方案构造
P7854
对于一个点想做别人的儿子，当且仅当它的权值\(a_i\)与父亲的权值\(a_j\)满足：\(a_j|a_i\).
所以，对于所有点，我们先按照权值大小从大到小排个序。
然后对于当前点\((u,a_u)\)将所有没有父亲节点并且\(a_u|a_v\)的点\(v\)连在\(u\)的下面。
同时，如果一个点有父亲节点\((p,a_p)\),\(a_v\)还是\(a_u\)的倍数，并且\(\gcd(a_p,a_u)=a_u\),说明\(a_p\)一定可以作为\(a_u\)的子节点(因为从大到小考虑，所以\(a_u\)一定比\(a_p\)小)，那么跳过不用处理；
否则，说明\(a_p\)不能作为\(a_u\)的子节点，那么\(v\)同时有两个根节点\(u,p\)，不满足，输出\(-1\).
建完树后，这棵树满足所有节点有唯一父亲节点并且权值都是父亲节点的倍数。
那么我们还需要判断是否出现\(\gcd(i,j)=k\)且\(k\)没出现过的情况。
如：
3
1 4 6
这种。
首先，将所有出现过的，是\(k\)倍数的节点拿出来。如果这些节点在原树种组成了多颗子树，那么说明这些子树的根节点权值两两求\(\gcd\)一定能求出\(k\),而\(k\)不存在，则无解.
否则，如果只有一颗子树，就只会求出那个根节点，不会求出\(k\)。
那么怎么判断呢？我们直接判断这些节点是否有父亲，或者其父亲节点是不是\(k\)的倍数时，如果没有父亲或者没有是\(k\)倍数的父亲，说明它是某颗子树的根节点，计数器加一；当计数器\(>1\)时，就无解了。
所以最终复杂度\(O((n+m)\log n)\)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10,M=1e6+10;
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int n,cnt;
int fa[N],b[N],f[M],head[N];
vector<int> vis[M];
struct node{
int id,val;
}a[N];
bool cmp(node a,node b){
return a.val>b.val;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i].val),a[i].id=i,b[i]=a[i].val,vis[a[i].val].push_back(a[i].id);
sort(a+1,a+n+1,cmp);
int lst=0,flag=1;
for(int i=1;i<=n;++i){
int pre=a[i].id;
if(lst==a[i].val) continue;
for(int j=a[i].val;j<M;j+=a[i].val){
if(vis[j].size()){
for(int k=0;k<vis[j].size();++k){
int now=vis[j][k];
if(now==pre) continue;
if(!fa[now]) fa[now]=pre;
else{
int g=gcd(b[fa[now]],b[pre]);
if(g!=b[pre]) flag=0;
}
}
}
}
lst=a[i].val;
}
for(int i=1;i<M;++i){
int tmp=0;
for(int j=i;j<M;j+=i){
if(vis[j].size()){
for(int k=0;k<vis[j].size();++k){
int now=vis[j][k];
if(fa[now]==0 || b[fa[now]]%i!=0) ++tmp;
}
}
}
if(tmp>1){
flag=0;break;
}
}
if(!flag) printf("-1");
else for(int i=1;i<=n;++i) printf("%d ",fa[i]);
return 0;
}
P3557
注意到距离为1的情况的最优解就是距离为2的情况的一个可行解,因为距离为1时，两个塔之间最多只能间隔两个节点，这样才能保证塔数量最少且覆盖全图,而这种构造方式等价于距离为2的情况下将所有未覆盖的节点选作塔，并覆盖上周围点的构造方式。而题目保证一定可以构造出等于\(k\)的最优解\(1\)。因此这种构造方式一定能构造出\(\leq k\)的可行解\(2\)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+10,M=1e6+10;
int n,m,k,cnt,u,v;
int head[N],ans[N],vis[N];
struct edge{
int v,nxt;
}e[M<<1];
void add(int u,int v){
e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void dfs(int u,int p,int dep){
vis[u]=1;
if(dep>=2) return;
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].v;
if(v==p) continue;
dfs(v,u,dep+1);
}
}
int main(){
memset(head,-1,sizeof head);cnt=-1;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(int i=1;i<=n;++i) if(!vis[i]) ans[++ans[0]]=i,dfs(i,0,0);
printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];++i) printf("%d ",ans[i]);
return 0;
}
P5441
~~名副其实的MO题~~
初始答案显然，为\(C_n^4\)
定义\(S_k\)表示\(i\to ((i+k-1)\mod n+1)\)的所有边的集合,即跳过了\(k-1\)个点。\(S_k=S_{n-k},|S_k|=\frac n2\)
注意到最外层\(S_1\)/次外层\(S_2\)的边都可以按照一个方向放置，不需要双向边，对答案没有影响。
而对于\(k\geq 3\)的情况，由于前两层的边是按照一个方向放置的，所以会出现两个不同方向的环共用这一条边，即需要双向边。如果不用双向边，就会丢失一部分方案数。
那么我们贪心地取两环中最大环的方向作为这条边的方向，丢失一部分最小环上的方案数,这种边的数量为\(n\)条。(两环相等任取一个，但注意边数只有\(\frac n2\)条)
可以发现\(S_k\)的所有边可以组成所有点数为\(k\)的环。
小环方案数\(=C_{k-2}^2\),因为一个边的两个点一定要取，不然状态有重复。
那么我们按照从小到大的顺序，减去这些贡献，最后剩下的就是最大方案数。
至于方案，只需要在统计\(k\geq 3\)边的时候记录一下两个端点，将减去的设为单向，剩下的设为双向即可。再加上\(k\leq 2\)即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,M=1e5+10;
int C[N],c[N],f[N][N];
int n,cnt,sum,m;
struct node{
int u,v,w;
node(int uu=0,int vv=0,int ww=0){
u=uu,v=vv,w=ww;
}
}ans[M];
void work(){
C[4]=1;c[2]=1;
for(int i=5;i<=n;++i) C[i]=C[i-1]*i/(i-4);
for(int i=3;i<=n;++i) c[i]=c[i-1]*i/(i-2);
cnt=0;sum=C[n];
for(int i=1;i<=n;++i)
for(int j=1;j<=2;++j) f[i][(i+j-1)%n+1]=1,f[i][i]=0;
for(int i=4;i<=n-i+2;++i){
int tmp=c[i-2];
if(i==n-i+2) for(int j=1;j<=n/2;++j) ans[++cnt]=node(j,(j+i-1-1)%n+1,tmp);//对应两环大小相等的情况。
else for(int j=1;j<=n;++j) ans[++cnt]=node(j,(j+i-1-1)%n+1,tmp);
}
m=max(0,n*(n-7)/2);
for(int i=1;i<=m;++i){
int u=ans[i].u,v=ans[i].v,w=ans[i].w;
sum-=w;f[u][v]=1;
}
for(int i=m+1;i<=cnt;++i){
int u=ans[i].u,v=ans[i].v;
f[u][v]=f[v][u]=1;
}
}
int main(){
scanf("%d",&n);
work();
printf("%d\n",sum);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j) printf("%d ",f[i][j]);
printf("\n");
}
return 0;
}