首页 > 其他分享 >路径计数 6.20西安集训(最短哈密顿回路条数)

路径计数 6.20西安集训(最短哈密顿回路条数)

时间:2023-06-20 16:45:24浏览次数:46  
标签:哈密顿 -- ++ long else 条数 int 6.20 mod

 

因为是哈密顿回路,所以每个点度数为2

假设我们已经考虑了i个点,其中b个B,w个W。

若存在x条由{1,2,...n}连向{i+1,...2n},

那么{1...n}内部的连边数为(2*i-x)/2

而只有不同颜色的点会连边,故(2*i-x)/2<=2*min(w,b)

x>=2(w+b)-4min(w,b)=2|w-b|

则x>=2max(1,|w-b|).

为了求得最短路,我们肯定希望x尽可能的小。而通过归纳法可以证明,这个下界一定可以取到。(虽然我不会证)(这真的需要大胆假设)

于是,我们观察取到下界时的性质。设fi 为考虑i个点的方案数

若w=b,则无论接下来是什么,都只有一种连接方法

若w>b

  若si+1=W,那么只能新开一条路径,因此f【i】=f【i-1】

  若si+1=B

    若w=b+1,这个B可以接在左右两侧,故f【i】=2*f【i-1】

    若w>b+1,那么就会有w-b条形如WBWBWBW的单独的回路,那么把B放入其中一条,再从剩下的(w-b-1)的回路中选择一条,接到B上,故f【i+1】=(w-b)(w-b-w)*f[i].

若w<b,对称过来即可。

直接递推,O(n)的复杂度

但是,我们在统计的时候,把

W1-->B-->W2

W1<--B<--W2

W2-->B-->W1

W2<--B<--W1

算成了4种,而实际上这只能算一种。

因此最后的答案为f【2n】/4  (还需注意除法取模)

(判断时的逻辑关系不能搞混)

所以,边权唯一的用处就是告诉我们要让x尽可能小。。。。。。

细节见代码

// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 1e7 + 666;
const int mod = 998244353;
int w, b, T, n;
ll f[N];
char c;
signed main() {
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);

    cin >> T;
    while (T--) {
        cin >> n;
        n <<= 1;
        w = 0;
        b = 0;
        f[0] = 1;
        /*for(int i=1;i<=1;i++){
                cin>>c;
                if(c=='W') w++;
                else b++;
        }*/
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            cin >> c;

            if (w == b) {
                f[i] = f[i - 1];
            } else if ((c == 'W') == (w > b))
                f[i] = f[i - 1];
            else if (w == b + 1 || b == w + 1) {
                f[i] = f[i - 1] * 2 % mod;
            } else if (w > b) {
                if (c == 'W')
                    f[i] = f[i - 1];
                else
                    f[i] = f[i - 1] * (w - b) % mod * (w - b - 1) % mod;
            } else {
                if (c == 'B')
                    f[i] = f[i - 1];
                else
                    f[i] = f[i - 1] * (b - w) % mod * (b - w - 1) % mod;
            }

            if (c == 'W')
                w++;
            else
                b++;
            // cout<<i<<" "<<w<<" "<<b<<" "<<f[i]<<endl;
        }
        // cout<<f[n]*2%mod<<endl;
        // cout<<f[n]<<"   ";
        printf("%lld\n", 1ll * f[n] * (mod / 2 + 1) % mod * (mod / 2 + 1) % mod);
    }
    return 0;
}
View Code

 

标签:哈密顿,--,++,long,else,条数,int,6.20,mod
From: https://www.cnblogs.com/DongPD/p/17494019.html

相关文章

  • 10万条数据批量更新怎么做?
    如果10万条数据进行批量更新该怎么操作呢?我们一起来看看具体可以怎么做。mysql批量更新如果一条条去更新效率是相当的慢,循环一条一条的更新记录,一条记录update一次,这样性能很差,也很容易造成阻塞。mysql批量更新共有以下四种办法1、.replaceinto批量更新replace into ......
  • Gorm使用的一些经验--如何彻底删除一条数据
    中文文档:https://gorm.io/zh_CN/我们知道,在使用gorm的时候,如果我们使用了gorm内置的model,会存在一个delete_at字段,当我们删除一条数据,这条数据并不会在数据库中被彻底删除举个例子:数据库中的数据如下: 现在通过实现的接口,去删除id=402的数据,在这里因为我设计的接口原......
  • MySQL数据库10秒内插入百万条数据
    publicclassBaseDao{//静态工具类,用于创建数据库连接对象和释放资源,方便调用//导入驱动jar包或添加Maven依赖(这里使用的是Maven,Maven依赖代码附在文末)static{try{Class.forName("com.mysql.cj.jdbc.Driver");}catch(Cla......
  • 使用virustotal VT 查询情报——感觉远远没有微步、思科好用,10万条数据查出来5万条都
    1399gitclonehttps://github.com/VirusTotal/c-vtapi.git1400cdc-vtapi/1402sudoapt-getinstallautomakeautoconflibtoollibjansson-devlibcurl4-openssl-dev1407autoreconf-fi1408./configure--enable-examples1409make1410sudomake......
  • 使用存储过程循环往MySQL插入1000条数据
    #新建一个存储过程delimiter//dropprocedureifexistslooppc;createprocedurelooppc()begindeclareiint;seti=1;repeatinsertintosome_table(t_id,t_name,t_age)values(i,'中心点',3+i);seti=i+1;untili>=1000endrepeat;en......
  • 统计这行有多少条数据
    DATA(LV_LINES)=REDUCEI(INITX=0FORLS_TEMPINGT_ALVWHERE(SEL='X'ANDLIGHTS='@08@')NEXTX=X+1).IFLV_LINES=0.MESSAGE'请选择要操作的数据,红灯数据不能操作'TYPE......
  • 分页查询设置每页多少条数据
    intpageIndex=request.getParameter("pageIndex")==null?1:Integer.parseInt(request.getParameter("pageIndex"));intpageSize=request.getParameter("pageSize")==null?15:Integer.parseInt(request.getParameter("p......
  • python3 获取mongodb表中数据的条数
    说明:此处考虑了时区,mongodb默认使用"格林威治时间"1#!/usr/bin/python323importpymongo4importdatetime5importpytz67#统计8"""9/usr/bin/pip3install-Ivpymongo-ihttp://pypi.douban.com/simple/--trusted-hostpypi.douban.com......
  • python 操作 PostgreSQL 数据库,线程并行修改 5w 条数据,性能优化
    python操作PostgreSQL数据库,线程并行修改5w条数据,性能优化110 娃哈哈店长的个人博客 /  433 /  0 / 创建于 3年前  获取新xls表中的所有数据并整理为列表形式返回其实修改的代码量不大,但是要考虑保留之前我们用的函数和方法还要继续能使用。excel2......
  • Linq 分组后取每一组时间最新的一条数据
    sqlSELECT*FROM(selectROW_NUMBER()over(partitionbyIdorderbyCollTimedesc)ASnewIndex,*fromTable)asTwhereT.newIndex=1结果: lambdavarquery=_repository.GetAll().GroupBy(r=>r.Id).Select(p=>p.OrderByDescending(r=>r.Coll......