模拟火车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)


相关推荐

  • 华中农业大学python实验题

    华中农业大学python实验题华中农业大学Python部分实验题,旨在为大家提供思路,希望大家抱着借鉴的心理来学习,不要直接抄袭。

  • int使用规则_single是什么数据类型

    int使用规则_single是什么数据类型先说结论吧,方便快速查询验证。总结区别int类型大小为8字节int8类型大小为1字节int16类型大小为2字节int32类型大小为4字节int64类型大小为8字节go语言中的int的大小是和操作系统位数相关的,如果是32位操作系统,int类型的大小就是4字节;如果是64位操作系统,int类型的大小就是8个字节取值范围int8:-128~127int16:-32768~32767int32:-2147483648~214

  • git 更新代码到本地

    git 更新代码到本地正规流程gitstatus(查看本地分支文件信息,确保更新时不产生冲突)gitcheckout–[filename](若文件有修改,可以还原到最初状态;若文件需要更新到服务器上,应该先merge到服务器,再更新到本地)gitbranch(查看当前分支情况)gitcheckoutremotebranch(若分支为本地分支,则需切换到服务器的远程分支)git…

  • 函数类型_C语言函数类型

    函数类型_C语言函数类型函数类型在ECMAScript中有三种函数类型:函数声明,函数表达式和函数构造器创建的函数。每一种都有自己的特点。1.函数声明这种函数类型的主要特点在于它们仅仅影响变量对象。该特点也解释了第二

  • page.RegisterStartupScript 方法

    page.RegisterStartupScript 方法注意:此API现在已过时。在页响应中发出客户端脚本块。允许asp.net服务器控件在page中发出客户端脚本块。page.RegisterStartupScript(key,)参数key标识脚本块的唯一键。script要发送到客户端的脚本的内容。以下是一些应用实例:打开一个新窗口:   page.registerstartupscr

  • pycharm2021专业版激活码【注册码】

    pycharm2021专业版激活码【注册码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

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

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