当前位置: 首页 > article >正文

P5684 [CSP-J2019 江西] 非回文串 题解

https://www.luogu.com.cn/problem/P5684

/*
比较简单的组合计数
题目没有以文字去描述,而是用下标来形式化题意,给我们一个关键信息:判定两个串是否相同不是看字符是否相同,而是看下标
换言之就是相同的字符,如果下标不同就算不同。这实际上更好算了进入正题:直接算非回文串很难,考虑正难则反,用总数n!减去回文串个数,就是非回文串个数
首先桶排,如果有>1种字符的数量为奇数,显然永远不可能排列成回文串(答案n!)
然后想想回文串个数怎么算:由于回文串的对称性考虑把回文串劈成两半,先确定一半里的字符,然后另一半的自然就对称过去了分情况讨论:(设t为桶数组)
1.所有字符个数都为偶数。直接按照上面的说法对称:(n/2)! * (t[1]!×t[2]!×...×t[26]!) / [(t[1]/2)!×(t[2]/2)!×...×(t[26]/2)!] = $\frac{\left(\frac{n}{2}\right)! \cdot \prod_{i = 1}^{26} t[i]!}{\prod_{i = 1}^{26} \left(\frac{t[i]}{2}\right)!}$组合意义:先确定左半边的排列(n/2)!,然后乘上变换下标顺序的方案数(为阶乘级别),但这样会多算因为(n/2)!已经考虑过左半边的顺序了,所以把这部分除掉,仅保留右边不同下标顺序的排列数
还有一种算法,先一个一个选左边哪些位置排什么字符(组合数),再乘上全排列的下标顺序方案数:=C(n/2,t[1]/2) * C(n/2-t[1]/2,t[2]/2) * C(n/2-t[1]/2-t[2]/2,t[3]/2) *...* (t[1]!×t[2]!×...×t[26]!)化简后是一样的2.只有一个字符个数为奇数,就把是奇数的那个排在最中间,然后两边对称排即可(就是在上面的情况下多乘一个选中间位置下标的方案数):
坑点:如果有出现奇数个的,在最中间的那个已经固定,所以要少算一次!!!
设字符p出现奇数次,=(n/2)! * (t[1]!×t[2]!×...×(t[p]-1)!×...×t[26]!) / [(t[1]/2)!×(t[2]/2)!×...×((t[p]-1)/2)!×...×(t[26]/2)!] * t[p] = $(\frac{n}{2})! \times \frac{(t[1]! \times t[2]! \times \cdots \times (t[p]-1)! \times \cdots \times t[26]!)}{(\frac{t[1]}{2}!) \times (\frac{t[2]}{2}!) \times \cdots (\frac{t[p]-1}{2}!) \times \cdots \times (\frac{t[26]}{2}!)} \cdot t[p]$考虑预处理一个阶乘和阶乘逆元即可
*/#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2005, mod = 1e9 + 7;ll Pow(ll x, ll y){ll ans = 1;while(y){if(y & 1) ans=ans*x%mod;x=x*x%mod, y>>=1;}return ans;
}int n, t[26];
string s;
ll fac[maxn], ifac[maxn];void solve()
{cin >> n >> s;// 预处理fac[0] = 1;for(int i = 1; i <= n; i ++){fac[i] = fac[i - 1] * i % mod;}ifac[n] = Pow(fac[n], mod - 2);for(int i = n - 1; i >= 0; i --){ifac[i] = ifac[i + 1] * (i + 1) % mod;}// 桶排 + 特判for(char c : s) t[c-'a'] ++;bool flag = false; int p = -1; // 是否出现个数为奇数的字符、位置for(int i = 0; i < 26; i ++){if((t[i] & 1) && flag){ // 说明不止一个字符出现奇数次,不可能出现回文串,答案即为全排列cout << fac[n]; return ;}else if(t[i] & 1) flag = true, p = i;}// 算答案ll cnt = fac[n / 2]; // 非回文串个数for(int i = 0; i < 26; i ++){if(i == p){ // 特判cnt = cnt * fac[t[i] - 1] % mod * ifac[(t[i] - 1) / 2] % mod;}else{cnt = cnt * fac[t[i]] % mod * ifac[t[i] / 2] % mod;}}if(flag) cnt = cnt * t[p] % mod;ll ans = (fac[n] - cnt + mod) % mod; // 别忘了加mod防止负数cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}

相关文章:

P5684 [CSP-J2019 江西] 非回文串 题解

https://www.luogu.com.cn/problem/P5684 /* 比较简单的组合计数 题目没有以文字去描述&#xff0c;而是用下标来形式化题意&#xff0c;给我们一个关键信息&#xff1a;判定两个串是否相同不是看字符是否相同&#xff0c;而是看下标 换言之就是相同的字符&#xff0c;如果下标…...

自适应移动平均(Adaptive Moving Average, AMA)

文章目录 1. 考夫曼自适应移动平均 (KAMA)算法推导及Python实现2. 对 (KAMA)算法参数进行优化及实现 自适应移动平均&#xff08;Adaptive Moving Average, AMA&#xff09;由Perry Kaufman在其著作《Trading Systems and Methods》中提出&#xff0c;它通过动态调整平滑系数来…...

Java密码加密存储算法,SpringBoot 实现密码安全存储

文章目录 一、写在前面二、密码加密存储方式1、基于MD5加盐方式2、SHA-256 Salt&#xff08;不需要第三方依赖包&#xff09;3、使用 BCrypt 进行哈希4、使用 PBKDF2 进行哈希5、使用 Argon2 进行哈希6、SCrypt 一、写在前面 日常开发中&#xff0c;用户密码存储是严禁明文存…...

使用 Version Catalogs统一配置版本 (Gradle 7.0+ 特性)

1.在 gradle/libs.versions.toml 文件中定义&#xff1a; [versions] compileSdk "34" minSdk "21" targetSdk "34" 2. 在 build.gradle 中使用&#xff1a; android {compileSdkVersion libs.versions.compileSdk.get().toInteger()defaul…...

涨薪技术|0到1学会性能测试第95课-全链路脚本开发实例

至此关于系统资源监控、apache监控调优、Tomcat监控调优、JVM调优、Mysql调优、前端监控调优、接口性能监控调优的知识已分享完,今天学习全链路脚本开发知识。后续文章都会系统分享干货,带大家从0到1学会性能测试。 前面章节介绍了如何封装.h头文件,现在通过一个实例来介绍…...

C++文件和流基础

C文件和流基础 1. C文件和流基础1.1 文件和流的概念1.2 标准库支持1.3 常用文件流类ifstream 类ofstream 类fstream 类 2.1 打开文件使用构造函数打开文件使用 open() 成员函数打开文件打开文件的模式标志 2.2 关闭文件使用 close() 成员函数关闭文件关闭文件的重要性 3.1 写入…...

Spring AI Alibaba + Nacos 动态 MCP Server 代理方案

作者&#xff1a;刘宏宇&#xff0c;Spring AI Alibaba Contributor 文章概览 Spring AI Alibaba MCP 可基于 Nacos 提供的 MCP server registry 信息&#xff0c;建立一个中间代理层 Java 应用&#xff0c;将 Nacos 中注册的服务信息转换成 MCP 协议的服务器信息&#xff0c…...

MCP:让AI工具协作变得像聊天一样简单 [特殊字符]

想象一下,你正在处理一个项目,需要从A平台查看团队讨论,从B平台获取客户信息,还要在GitHub上检查代码进度。传统做法是什么?打开三个不同的网页,在各个平台间来回切换,复制粘贴数据,最后还可能因为信息分散而遗漏重要细节。 听起来很熟悉?这正是当前工作流程的痛点所…...

C++ Learning string类模拟实现

string类模拟实现 std::string 类作为 C 标准库中非常重要的一个类型&#xff0c;它封装了字符串的动态分配、内存管理以及其他字符串操作。 基本构思与设计 一个简化版的 string 类需要满足以下基本功能&#xff1a; 存储一个字符数组&#xff08;char*&#xff09;。记录…...

Message=“HalconDotNet.HHandleBase”的类型初始值设定项引发异常

该异常通常与HalconDotNet库的版本冲突或环境配置问题有关&#xff0c;以下是常见解决方案&#xff1a; ‌版本冲突处理‌ 检查项目中是否同时存在多个HalconDotNet引用&#xff08;如NuGet安装和本地引用混用&#xff09;&#xff0c;需删除所有冲突引用并统一版本2确保工具…...

AI炼丹日志-27 - Anubis 通过 PoW工作量证明的反爬虫组件 上手指南 原理解析

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; Java篇&#xff1a; MyBatis 更新完毕目前开始更新 Spring&#xff0c;一起深入浅出&#xff01; 大数据篇 300&#xff1a; Hadoop&…...

阿姆达尔定律的演进:古斯塔夫森定律

前言 在上一篇文章《使用阿姆达尔定律来提升效率》中提到的阿姆达尔定律前提是假设问题的规模保持不变&#xff0c;并且给定一台速度更快的机器&#xff0c;目标是更快地解决问题。然而&#xff0c;在大多数情况下&#xff0c;这并不完全正确。当有一台更快的机器时&#xff0…...

JavaScript极致性能优化全攻略

JavaScript性能优化深度指南 1 引言 JavaScript性能优化在现代Web开发中至关重要。随着Web应用日益复杂,性能直接影响用户体验、搜索引擎排名和业务转化率。研究表明,页面加载时间每增加1秒,转化率下降7%,跳出率增加32%。通过优化JavaScript性能,开发者可以: 提升用户满…...

批量大数据并发处理中的内存安全与高效调度设计(以Qt为例)

背景 在批量处理大型文件(如高分辨率图片、视频片段、科学数据块)时,开发者通常希望利用多核CPU并行计算以提升处理效率。然而,如果每个任务对象的数据量很大,直接批量并发处理极易导致系统内存被迅速耗尽,出现程序假死、崩溃,甚至系统级“死机”。 Qt自带的线程池(Q…...

Transformer核心原理

简介 在人工智能技术飞速发展的今天&#xff0c;Transformer模型凭借其强大的序列处理能力和自注意力机制&#xff0c;成为自然语言处理、计算机视觉、语音识别等领域的核心技术。本文将从基础理论出发&#xff0c;结合企业级开发实践&#xff0c;深入解析Transformer模型的原…...

Grafana-State timeline状态时间线

显示随时间推移的状态变化 状态区域&#xff1a;即状态时间线上的状态显示的条或带&#xff0c;区域长度表示状态持续时间或频率 数据格式要求&#xff08;可视化效果最佳&#xff09;&#xff1a; 时间戳实体名称&#xff08;即&#xff1a;正在监控的目标对应名称&#xf…...

解决CSDN等网站访问不了的问题

原文网址&#xff1a;解决CSDN等网站访问不了的问题-CSDN博客 简介 本文介绍解决CSDN等网站访问不了的方法。 问题描述 CSDN访问不了了&#xff0c;页面是空的。 问题解决 方案1&#xff1a;修改DNS 可能是dns的问题&#xff0c;需要重新配置。 国内常用的dns是&#x…...

【华为云Astro Zero】组装设备管理页面开发(图形拖拽 + 脚本绑定)

目录 🧠 一、核心原理概览(类比说明) 🛠 二、完整操作步骤(详细图形拖拽流程) 1. 创建项目页面骨架 2. 定义设备信息的数据模型 equipmentInstance 3. 定义服务模型(接口绑定机器人搬运逻辑) 4. 拖拽组件搭建界面结构 4.1 表格: 4.2 工具栏按钮(新增) 4.…...

PopupImageMenuItem 无响应

Popup Menu | GNOME JavaScript let menuItem new PopupMenu.PopupImageMenuItem(设置, settings, {}); 第三个参数 params (Object) — Additional item properties 写了个 {}&#xff0c;我就以为是 function&#xff0c;我还改成了 () > {} ! 正常是通过 connect 响…...

C++ Vector算法精讲与底层探秘:从经典例题到性能优化全解析

前引&#xff1a;在C标准模板库&#xff08;STL&#xff09;中&#xff0c;vector作为动态数组的实现&#xff0c;既是算法题解的基石&#xff0c;也是性能优化的关键战场。其连续内存布局、动态扩容机制和丰富的成员函数&#xff0c;使其在面试高频题&#xff08;如LeetCode、…...

Flowith,有一种Agent叫无限

大家好&#xff0c;我是羊仔&#xff0c;专注AI工具、智能体、编程。 今天羊仔要和大家聊聊一个最近发现的超级实用的Agent平台&#xff0c;名字叫Flowith。 这篇文章会带你从零了解到实战体验&#xff0c;搞清楚Flowith是如何让工作效率飙升好几倍&#xff0c;甚至重新定义未…...

系统思考:短期利益与长期系统影响

一个决策难题&#xff1a;一家公司接到了一个大订单&#xff0c;客户提出了10%的降价要求&#xff0c;而企业的产能还无法满足客户的需求。你会选择增加产能&#xff0c;接受这个订单&#xff0c;还是拒绝&#xff1f;从系统思考的角度来看&#xff0c;这个决策不仅仅是一个简单…...

大数据 ETL 工具 Sqoop 深度解析与实战指南

一、Sqoop 核心理论与应用场景 1.1 设计思想与技术定位 Sqoop 是 Apache 旗下的开源数据传输工具&#xff0c;核心设计基于MapReduce 分布式计算框架&#xff0c;通过并行化的 Map 任务实现高效的数据批量迁移。其特点包括&#xff1a; 批处理特性&#xff1a;基于 MapReduc…...

【学习记录】Django Channels + WebSocket 异步推流开发常用命令汇总

文章目录 &#x1f4cc; 摘要&#x1f9f0; 虚拟环境管理✅ 创建虚拟环境✅ 删除虚拟环境✅ 激活/切换虚拟环境 &#x1f6e0;️ Django 项目管理✅ 查看 Django 版本✅ 创建 Django 项目✅ 创建 Django App &#x1f4ac; Channels 常用操作✅ 查看 Channels 版本 &#x1f50…...

(四)动手实现多层感知机:深度学习中的非线性建模实战

1 多层感知机&#xff08;MLP&#xff09; 多层感知机&#xff08;Multilayer Perceptron, MLP&#xff09;是一种前馈神经网络&#xff0c;包含一个或多个隐藏层。它能够学习数据中的非线性关系&#xff0c;广泛应用于分类和回归任务。MLP的每个神经元对输入信号进行加权求和…...

HTTP连接管理——短连接,长连接,HTTP 流水线

连接管理是一个 HTTP 的关键话题&#xff1a;打开和保持连接在很大程度上影响着网站和 Web 应用程序的性能。在 HTTP/1.x 里有多种模型&#xff1a;短连接、_长连接_和 HTTP 流水线。 下面分别来详细解释 短连接 HTTP 协议最初&#xff08;0.9/1.0&#xff09;是个非常简单的…...

【免费】2004-2020年各省电力消费量数据

2004-2020年各省电力消费量数据 1、时间&#xff1a;2004-2020年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;行政区划代码、地区、年份、电力消费量(亿千瓦小时) 4、范围&#xff1a;31省 5、指标说明&#xff1a;电力消费量是指在一定时期内&#xff…...

Python编程基础(四) | if语句

引言&#xff1a;很久没有写 Python 了&#xff0c;有一点生疏。这是学习《Python 编程&#xff1a;从入门到实践&#xff08;第3版&#xff09;》的课后练习记录&#xff0c;主要目的是快速回顾基础知识。 练习1&#xff1a;条件测试 编写一系列条件测试&#xff0c;将每个条…...

登录的写法,routerHook具体配置,流程

routerHook挂在在index.js/main.js下的&#xff0c;找不到可以去那边看一下 vuex需要做的&#xff1a; //创建token的sate&#xff0c;从本地取 let token window.localStorage.getItem(token) // 存储用户登录信息let currentUserInfo reactive({userinfo: {}}) //存根据不…...

Java-IO流之字节输出流详解

Java-IO流之字节输出流详解 一、Java字节输出流基础概念1.1 Java IO体系与字节输出流的位置1.2 字节输出流的核心类层次结构 二、OutputStream接口核心方法详解2.1 void write(int b)2.2 void write(byte[] b)2.3 void write(byte[] b, int off, int len)2.4 void flush()2.5 v…...