模拟火车2019中国线路手机版_com.neon.cube2048

模拟火车2019中国线路手机版_com.neon.cube2048jzoj6009. 【THUWC2019模拟2019.1.18】Counting (dp)

大家好,又见面了,我是你们的朋友全栈君。

Description

羽月最近发现,她发动能力的过程是这样的:
构建一个 V 个点的有向图 G,初始为没有任何边,接下来羽月在脑中构建出一个长度为 E 的边的序列,序列中元素两两不同,然后羽月将这些边依次加入图中,每次加入之后计算当前图的强连通分量个数并记下来,最后得到一个长度为E 的序列,这个序列就是能力的效果。
注意到,可能存在边的序列不同而能力效果相同的情况,所以羽月想请你帮她计算能发动的不同能力个数,答案对 998244353 取模。你需要对于1<=E<=V*(V-1)的所有 E 计算答案。

Data Constraint

对于 10%的数据,1<=V<=5
对于 30%的数据,1<=V<=20
对于 60%的数据,1<=V<=50
对于 100%的数据,1<=V<=100

solution

全场切的题目咱连题目都看不懂对咱来说已经是日常了

题解觉得这题太水于是只有一句话于是咱只好对着一份代码理解了半天

考虑一个策略,我们维护一条链\(1\)\(i\),如果连的下一条边需要不减少强连通分量个数,那么就连上\((i,i+1)\),如果需要减少强连通分量个数,那么就在链上选一个点向前连边

不难发现,每一种强连通分量序列的情况,都可以通过这种策略来表示

考虑\(dp\),设\(dp_{i,j,k}\)表示连了\(i\)条边,上面有\(j\)个点已经在强连通分量里了,对于链维护到了\(1\)\(k\),那么枚举下一条边,考虑它是未增加强连通分量个数或者减少的强连通分量个数,转移即可

还有一种尴尬的情况就是点全都连完了,但我们还需要使强连通分量个数不变,这种时候往前连一条没用的边就行了

顺带注意,我们在连环边和无用边的时候可能会有边爆掉的情况,设链上有\(n\)个点,有\(j\)个在环里(即强连通分量),那么链上的每个点可以向后面的所有点连边,环上的每个点可以向前面的所有点连边,就算全部连满,边数也不能超过\(\frac{n(n+1)+j(j+1)}{2}\)

然后就没有然后了,理论上来说时间复杂度\(O(v^5)\),只要用刷表法,判断一下当前状态是否可行就行了

//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
inline int max(const R int &x,const R int &y){return x>y?x:y;}
inline int min(const R int &x,const R int &y){return x<y?x:y;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res=1,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
void print(R int x){
    if(K>1<<20)Ot();if(x<0)x=-x,sr[++K]='-';
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++K]=z[Z],--Z);sr[++K]=' ';
}
const int N=105,P=998244353;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
    return res;
}
int dp[N*N][N][N];
int n,res;
int main(){
//  freopen("testdata.in","r",stdin);
    freopen("counting.in","r",stdin);
    freopen("counting.out","w",stdout);
    scanf("%d",&n);
    dp[0][1][1]=1;
    fp(i,0,n*(n-1)-1)fp(j,1,min(n,i+1))fp(k,j,min(n,i+1))
    if(dp[i][j][k]){
        if(i<=k+j-2&&k<n)dp[i+1][j][k+1]=add(dp[i+1][j][k+1],dp[i][j][k]);
        else if(k*(k-1)+j*(j-1)>=(i+1<<1))dp[i+1][j][k]=add(dp[i+1][j][k],dp[i][j][k]);
        fp(l,1,k-j)
        if(k*(k-1)+(j+l)*(j+l-1)>=(i+1<<1))dp[i+1][j+l][k]=add(dp[i+1][j+l][k],dp[i][j][k]);
    }
    fp(i,1,n*(n-1)){
        res=0;
        fp(j,1,min(n,i+1))fp(k,j,min(n,i+1))res=add(res,dp[i][j][k]);
        print(res);
    }
    return Ot(),0;
}

转载于:https://www.cnblogs.com/bztMinamoto/p/10292866.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107045.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SVN常用命令之checkout

    SVN常用命令之checkout

    2021年10月21日
  • ICMP协议/IGMP协议详解

    ICMP协议/IGMP协议详解网际控制报文协议ICMP功能:ICMP允许主机或者路由器报告差多情况和提供有关异常情况的报告,它是网络层的协议,ICMP报文装在IP数据报中,作为其中的数据部分。ICMP报文的种类ICMP差错报文终点不可达源点抑制超时参数问题改变路由(重定向)ICMP询问报文回送请求和回答时间戳请求和回答ICMP应用举例ping(PacketInternetGroper)命令:该命令利用发送分

  • centos7卸载软件命令_linux安装docker

    centos7卸载软件命令_linux安装docker1首先搜索已经安装的docker安装包[root@localhost~]#yumlistinstalled|grepdocker或者使用该命令[root@localhost~]#rpm-qa|grepdockerdocker.x86_642:1.12.6-16.el7.centos@extras

  • pychorm激活码【中文破解版】

    (pychorm激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html0UY7RF7AC5-eyJsaWNlbnNlSWQi…

  • dynamin_Dynamite

    dynamin_Dynamite摘自《JEDEC78-3F》在某种应用情况下,为了更好的提高数据总线的信号完整性,我们需要DDR3SDRAM的终端阻抗可以不需要通过MRS命令来改变。这种需求由“动态ODT”特性来支持。

  • springBoot+mybatis报错Property ‘sqlSessionFactory’ or ‘sqlSessionTemplate’ are required

    springBoot+mybatis报错Property ‘sqlSessionFactory’ or ‘sqlSessionTemplate’ are required报错为:Invocationofinitmethodfailed;nestedexceptionisjava.lang.IllegalArgumentException:Property’sqlSessionFactory’or’sqlSessionTemplate’arerequired日志很长,报错在末尾2018-07-1213:56:41.760 I…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号