ZJT's Blog

大変に気分がいい~

[自选题 #145] 树

2017-12-25 12:92017-12-25 12:9
集训队作业自选题DP

传送门

我们把$B_i$差分得到$D_i=B_i-B_{fa_i}$,发现题目的限制其实就是$\sum D_i\leq Y$。考虑把一个树高为$i$的子树,把根的$D_i$加一后产生的贡献。记$S_i$为这个贡献,则$(S_i,X^i)$可以表示成$(S_{i-1},X^{i-1})$的线性转移。由于这两个东西都是在模$P$意义下的,所以这个$S_i$的循环节长度就是$P^2$级别的。这样,我们就能直接预处理出对于每个$k$,有多少个点$i$满足$S_{h_i}=k$。

然后,我们做一个三维的DP,设$f_{i,j,k}$表示当前处理了$S$的取值在$[0,i)$之间的的点,当前$D$的总和为$j$,且当前$\sum A_i\times B_i$模$P$为$k$。直接枚举如何选取贡献为$i$的点来转移就行了,复杂度是$O(Y^2P^2)$。

#include <bits/stdc++.h>
#define LL long long
#define MAXN 510
#define MAXM 12

const LL P=1000000007;

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

LL H,inv2=getPow(2,P-2);
int C,n,m;
LL cnt[MAXN];
LL c[MAXN][MAXM];
LL f[MAXN][MAXM][MAXN];

LL getC(LL x,LL y){
    LL t1=1,t2=1;
    for(int i=0;i<y;i++){
        t1=t1*(x-i)%P;
        t2=t2*(i+1)%P;
    }
    return t1*getPow(t2,P-2)%P;
}

void pre_gao(){
    static bool visit[MAXN][MAXN];
    static int v[MAXN*MAXN][2];
    int numv=1;
    int nx=C,ny=C;
    v[1][0]=nx;
    v[1][1]=getPow(2,H-1);
    visit[nx][ny]=1;
    for(int i=2;;i++){
        ny=ny*C%m;
        nx=(nx*2+ny)%m;
        if(visit[nx][ny]) break;
        v[++numv][0]=nx;
        v[numv][1]=v[numv-1][1]*inv2%P;
        visit[nx][ny]=1;
    }
    LL step=getPow(inv2,numv);
    for(int i=1;i<=numv;i++){
        LL t1=H/numv;
        if(i<=H%numv) t1++;
        LL t2=v[i][1]*(getPow(step,t1)-1)%P*getPow(step-1,P-2)%P;
        cnt[v[i][0]]=(cnt[v[i][0]]+t2)%P;
    }
    for(int i=0;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])%P;
    }
    for(int i=0;i<m;i++)
        for(int j=0;j<=n;j++)
            c[i][j]=getC(cnt[i]+j-1,j);
}

inline void update(LL &x,LL y){ x=(x+y)%P; }

LL dp(){
    f[0][0][0]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<m;k++)
                for(int x=0;x<=n-j;x++)
                    update(f[i+1][j+x][(k+i*x)%m],f[i][j][k]*c[i][x]);
    LL ans=0;
    for(int i=0;i<=n;i++)
        update(ans,f[m][i][0]);
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("145.in","r",stdin);
#endif
    scanf("%lld%d%d%d",&H,&C,&n,&m);
    pre_gao();
    printf("%lld\n",dp());
    return 0;
}

查看详细内容

[自选题 #107] An unavoidable detour for home

2017-12-22 10:582017-12-22 10:58
集训队作业自选题DP

传送门

直接DP,设$f_{i,j_1,j_2,k_1,k_2}$表示“当前处理了包含在$\{1,\cdots,i\}$内的边,有$j_1$个点满足$l_x=l_i-1$且有一条边连向后面的点,有$j_2$个点满足$l_x=l_i-1$且有两条边连向后面的点,有$k_1$个点满足$l_x=l_i$且有一条边连向后面的点,有$k_2$个点满足$l_x=l_i$且有两条边连向后面的点”的方案数。枚举第$i+1$个点的连边情况即可,情况比较复杂。注意$d_1$可能为3,要把$l_x=1$的点单独拿出来处理一下。

#include <bits/stdc++.h>
#define MAXN 52
#define LL long long

const LL P=1000000007;

int n;
int d[MAXN];
LL f[2][MAXN][MAXN][MAXN][MAXN];
LL g2[MAXN];

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",d+i);
    for(int i=1;i<=n;i++) g2[i]=i*(i-1)/2;
    if(d[2]==2) f[0][0][0][1][0]=1;
    else f[0][0][0][0][1]=1;
    for(int i=3;i<=n;i++){
        int now=i&1,last=(i&1)^1;
        for(int t1=0;t1<=i;t1++)
            for(int t2=0;t1+t2<=i;t2++)
                for(int t3=0;t1+t2+t3<=i;t3++)
                    for(int t4=0;t1+t2+t3+t4<=i;t4++)
                        f[now][t1][t2][t3][t4]=0;
        if(i<=d[1]+1){
            for(int t1=0;t1<i;t1++)
                for(int t2=0;t1+t2<i;t2++)
                    for(int t3=0;t1+t2+t3<i;t3++)
                        for(int t4=0;t1+t2+t3+t4<i;t4++)
                            if(f[last][t1][t2][t3][t4]){
                                LL lastv=f[last][t1][t2][t3][t4];
                                if(d[i]==2){
                                    update(f[now][t1][t2][t3+1][t4],lastv);
                                    if(t3) update(f[now][t1][t2][t3-1][t4],lastv*t3);
                                    if(t4) update(f[now][t1][t2][t3+1][t4-1],lastv*t4);
                                }else{
                                    update(f[now][t1][t2][t3][t4+1],lastv);
                                    update(f[now][t1][t2][t3][t4],lastv*t3);
                                    if(t4) update(f[now][t1][t2][t3+2][t4-1],lastv*t4);
                                    if(t3>=2) update(f[now][t1][t2][t3-2][t4],lastv*g2[t3]);
                                    if(t4>=2) update(f[now][t1][t2][t3+2][t4-2],lastv*g2[t4]);
                                    if(t3&&t4) update(f[now][t1][t2][t3][t4-1],lastv*t3*t4);
                                }
                            }
        }else{
            for(int t1=0;t1<i;t1++)
                for(int t2=0;t1+t2<i;t2++)
                    for(int t3=0;t1+t2+t3<i;t3++)
                        for(int t4=0;t1+t2+t3+t4<i;t4++)
                            if(f[last][t1][t2][t3][t4]){
                                LL lastv=f[last][t1][t2][t3][t4];
                                if(d[i]==2){
                                    if(t1){
                                        update(f[now][t1-1][t2][t3+1][t4],lastv*t1);
                                        if(t3) update(f[now][t1-1][t2][t3-1][t4],lastv*t3*t1);
                                        if(t4) update(f[now][t1-1][t2][t3+1][t4-1],lastv*t4*t1);
                                    }
                                    if(t2){
                                        update(f[now][t1+1][t2-1][t3+1][t4],lastv*t2);
                                        if(t3) update(f[now][t1+1][t2-1][t3-1][t4],lastv*t3*t2);
                                        if(t4) update(f[now][t1+1][t2-1][t3+1][t4-1],lastv*t4*t2);
                                    }
                                    if(!t1 && !t2){
                                        if(t3) update(f[now][t3-1][t4][1][0],lastv*t3);
                                        if(t4) update(f[now][t3+1][t4-1][1][0],lastv*t4);
                                    }
                                }else{
                                    if(t1){
                                        update(f[now][t1-1][t2][t3][t4+1],lastv*t1);
                                        update(f[now][t1-1][t2][t3][t4],lastv*t3*t1);
                                        if(t4) update(f[now][t1-1][t2][t3+2][t4-1],lastv*t4*t1);
                                        if(t3>=2) update(f[now][t1-1][t2][t3-2][t4],lastv*g2[t3]*t1);
                                        if(t4>=2) update(f[now][t1-1][t2][t3+2][t4-2],lastv*g2[t4]*t1);
                                        if(t3&&t4) update(f[now][t1-1][t2][t3][t4-1],lastv*t3*t4*t1);
                                    }
                                    if(t2){
                                        update(f[now][t1+1][t2-1][t3][t4+1],lastv*t2);
                                        update(f[now][t1+1][t2-1][t3][t4],lastv*t3*t2);
                                        if(t4) update(f[now][t1+1][t2-1][t3+2][t4-1],lastv*t4*t2);
                                        if(t3>=2) update(f[now][t1+1][t2-1][t3-2][t4],lastv*g2[t3]*t2);
                                        if(t4>=2) update(f[now][t1+1][t2-1][t3+2][t4-2],lastv*g2[t4]*t2);
                                        if(t3&&t4) update(f[now][t1+1][t2-1][t3][t4-1],lastv*t3*t4*t2);
                                    }
                                    if(!t1 && !t2){
                                        if(t3) update(f[now][t3-1][t4][0][1],lastv*t3);
                                        if(t4) update(f[now][t3+1][t4-1][0][1],lastv*t4);
                                    }
                                }
                            }
        }
    }
    printf("%lld\n",f[n&1][0][0][0][0]);
}

查看详细内容

[自选题 #104] [UR #10] 列队

2017-12-20 19:412018-9-13 19:51
集训队作业自选题抽象代数DP容斥群论

传送门

这道题成功让我认识到了我的抽代基本等于没学。。。

题目问的是给定群$G$到$S_n$之间有多少种单同态,其中$S_n$是$n$阶对称群。

先考虑怎么把单同态的限制去掉。根据抽代中的一些理论,$\phi:G_1\to G_2$为单同态当且仅当$\ker \phi=\{e\}$,即$G_1$中只有单位元能映射到$G_2$的单位元。所以,我们只要枚举$G_1$除了$\{e\}$以外的所有正规子群$H$,递归算出满足$\ker \phi=H$的$\phi$有多少种(这等价于求$G_1/H$到$G_2$的单同态数目)。这时如果我们能求出$G_1\to G_2$的同态数目,就能直接容斥得到单同态数目了。

考虑怎么计算$G\to S_n$的同态数目。我们知道,$G\to S_n$的一个同态,对应了群$G$在$\{1,\dots,n\}$上的一个作用。显然,这个作用的轨道之间是独立的,我们可以把每个轨道单独拿出来考虑。

记$\{1,\cdots,n\}$中的某个轨道为$R$,$\phi:G\to S_{|R|}$为同态,则根据抽代中的结论,$|R|$整除$|G|$,且对于任意$r\in R$,$r$的稳定子群$G_r$的陪集和整个轨道$R$一一对应。可以证明(证明过程参见wyy题解),在$1$的稳定子群$G_1$确定的情况下(这里$1$也可以换成别的元素),同态的数目为$(|R|-1)!$,所以总的同态数目为$(|R|-1)!\times($$G$的大小为$\frac{|H|}{|R|}$的子群数$)$。

我们先预处理出$G$的每种大小的子群分别有多少个,然后就能DP啦。设$f_i$表示$G\to S_i$的同态数,我们考虑决策包含$1$的轨道,记$c_k=(k-1)!\times($$G$的大小为$\frac{|H|}k$的子群数$)$,则:$$f_i=\sum_{j=1}^ic_jf_{i-j}\binom{i-1}{j-1}$$

这样我们就完成了对$G\to S_n$的同态数目的统计。找子群可以用广搜,枚举加入的元素,然后跑出包含已有元素的最小子群。最后,容斥的时候有一个小技巧,根据群的第三同构定理,$G$的商群的正规子群一定对应了一个$G$的一个正规子群。所以我们只要在$G$的正规子群里面进行容斥就行了,这样就不用算商群了。总复杂度大概是$O(n_N(n_G+n|G|))$,其中$n_N$为正规子群数,$n_G$为子群数。由于$n_N$和$n_G$都很小,就能直接跑过去啦。

#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#define MAXN 40
#define MAXM 1010
#define LL long long
using namespace std;

const LL P=998244353;

int n,m;
int g[MAXN][MAXN],inv[MAXN],unit;
set<int> s_sg;
vector<int> sg,nsg;
LL c[MAXM][MAXM],fac[MAXM];
LL h[MAXM];

int extend(int s,int x){
    static queue<int> Q;
    s|=1<<(x-1);
    while(1){
        bool flag=0;
        for(int i=1;i<=n;i++)
            if(s&(1<<(i-1)))
                for(int j=1;j<=n;j++)
                    if(s&(1<<(j-1)))
                        if((~s)&(1<<(g[i][j]-1))){
                            flag=1;
                            s|=1<<(g[i][j]-1);
                        }
        if(!flag) return s;
    }
}

bool check_normal(int s){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((s&(1<<(j-1))) && ((~s)&(1<<(g[g[i][j]][inv[i]]-1))))
                return 0;
    return 1;
}

void bfs(){
    static queue<int> Q;
    for(int i=1;i<=n;i++){
        int x=extend(0,i);
        if(!s_sg.count(x)){
            s_sg.insert(x);
            Q.push(x);
        }
    }
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=1;i<=n;i++){
            int y=extend(x,i);
            if(!s_sg.count(y)){
                s_sg.insert(y);
                Q.push(y);
            }
        }
    }
    for(set<int>::iterator it=s_sg.begin();it!=s_sg.end();it++){
        if(check_normal(*it)) nsg.push_back(*it);
        sg.push_back(*it);
    }
}

void dp(int x){
    static int cnt[MAXN];
    memset(cnt,0,sizeof cnt);
    int s=nsg[x],sz=0;
    for(int l=1<<30;l;l>>=1) if(s&l) sz++;
    sz=n/sz;
    for(int i=0;i<sg.size();i++)
        if((sg[i]&s)==s){
            int temp=0;
            for(int l=1<<30;l;l>>=1) if(sg[i]&l) temp++;
            cnt[temp/(n/sz)]++;
        }
    static LL f[MAXM];
    f[0]=1;
    for(int i=1;i<=m;i++){
        f[i]=0;
        for(int j=1;j<=i && j<=sz;j++)
            if(sz%j==0)
                f[i]=(f[i]+c[i-1][j-1]*f[i-j]%P*cnt[sz/j]%P*fac[j-1])%P;
    }
    h[x]=f[m];
    for(int i=x+1;i<nsg.size();i++)
        if((nsg[i]&s)==s) h[x]=(h[x]-h[i])%P;
}

void solve(){
    s_sg.clear();
    sg.clear();
    nsg.clear();
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(g[i][g[j][k]]!=g[g[i][j]][k]){
                    puts("0");
                    return;
                }
    for(int i=1;i<=n;i++)
        if(g[i][i]==i) unit=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j]==unit)
                inv[i]=j;
    bfs();
    for(int i=nsg.size()-1;i>=0;i--) 
        dp(i);
    printf("%lld\n",(h[0]+P)%P);
}

void init(){
    for(int i=0;i<MAXM;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
    }
    fac[0]=1;
    for(int i=1;i<MAXM;i++) fac[i]=fac[i-1]*i%P;
}

int main(){
#ifdef DEBUG
    freopen("104.in","r",stdin);
#endif
    init();
    int T;
    scanf("%d",&T);
    while(T--) solve();
}

查看详细内容

集训队作业之ARC071-F

2017-12-18 12:202017-12-18 12:20
集训队作业AtCoderDP

传送门

容易发现只要有两个非1的数排在一起,后面的数就会一直重复了。所以只要枚举最后一个1的位置,然后分类讨论一下就做完啦。

哦对了要DP预处理一下最后一个1位于第$i$位时,第$i$位以前的方案数。转移用前缀和搞一下就行了。

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

const LL P=1000000007;

int n;
LL g[MAXN],sg[MAXN];

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
    scanf("%d",&n);
    g[0]=1;
    sg[0]=1;
    for(int i=1;i<=n;i++){
        g[i]=g[i-1];
        if(i>=3) g[i]=(g[i]+sg[i-3])%P;
        sg[i]=(sg[i-1]+g[i])%P;
    }
    LL ans=0;
    //a[n]=1
    update(ans,g[n-1]);
    for(int i=2;i<=n;i++){
        int j=n-i-1;
        if(j<0) j=0;
        update(ans,sg[n-2]-(j?sg[j-1]:0));
    }
    //a[n-1]=1
    update(ans,g[n-1]*(n-1));
    //else
    for(int i=0;i<=n-2;i++)
        update(ans,g[i]*(n-1)%P*(n-1));
    ans=(ans+P)%P;
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC066-E

2017-12-16 10:262017-12-16 10:26
集训队作业AtCoder结论题DP

传送门

有个结论就是三层以上的括号没有意义。。。有了这个结论随便DP一下就做完了。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

int n;
LL a[MAXN];
int b[MAXN];
LL f[MAXN][3];

inline void update(LL &x,LL y){ if(y>x) x=y; }

int main(){
    scanf("%d",&n);
    b[1]=1;
    scanf("%lld",a+1);
    for(int i=2;i<=n;i++){
        char c;
        while((c=getchar())==' ');
        b[i]=(c=='+'?1:-1);
        scanf("%lld",a+i);
    }
    memset(f,0x88,sizeof f);
    f[1][0]=a[1];
    for(int i=2;i<=n;i++)
        if(b[i]==1){
            update(f[i][0],f[i-1][0]+a[i]);
            update(f[i][0],f[i-1][1]+a[i]);
            update(f[i][0],f[i-1][2]+a[i]);
            update(f[i][1],f[i-1][1]-a[i]);
            update(f[i][1],f[i-1][2]-a[i]);
            update(f[i][2],f[i-1][2]+a[i]);
        }else{
            update(f[i][0],f[i-1][0]-a[i]);
            update(f[i][1],f[i-1][0]-a[i]);
            update(f[i][0],f[i-1][1]-a[i]);
            update(f[i][1],f[i-1][1]+a[i]);
            update(f[i][2],f[i-1][1]+a[i]);
            update(f[i][0],f[i-1][2]-a[i]);
            update(f[i][1],f[i-1][2]+a[i]);
            update(f[i][2],f[i-1][2]+a[i]);
        }
    printf("%lld\n",max(max(f[n][0],f[n][1]),f[n][2]));
    return 0;
}

查看详细内容