HDU 5651 xiaoxin juju needs help(BestCoder Round #77 (div.1)1001)

简介:

传送门

xiaoxin juju needs help

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 861    Accepted Submission(s): 243


Problem Description
As we all known, xiaoxin is a brilliant coder. He knew **palindromic** strings when he was only a six grade student at elementry school.

This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin's leader needs to buy?
 

Input
This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, there is a single line containing a string S(1≤length(S)≤1,000).
 

Output
For each test case, print an integer which is the number of watermelon candies xiaoxin's leader needs to buy after mod 1,000,000,007.
 

Sample Input
 
 
3 aa aabb a
 

Sample Output
 
 
1 2 1
 

Source
 

题目大意:

xiaoxin巨从小就喜欢字符串,六年级的时候他就知道了什么是回文串。这时,xiaoxin巨说到:如果一个字符串 SS 是回文串,那么该字符串从前往后看和从后往前看是一样一样的。

六年级的暑假,xiaoxin很快就做完了暑假作业,然后到腾讯做起了实习生。这日,leader给了xiaoxin一个字符串,请xiaoxin帮忙写一个函数来生成所有可能的回文串,可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin,每生成一个不一样的回文串就可以得到一颗西瓜糖。

请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢?
解题思路:

回文字符串的个数可以根据一个公式来推导一下:

条件:

1.len = strlen(str),len>>=1;

2.num[i]:表示的是字符串每个字符 -  'a' 的个数,然后将其除以2;

结果: ret  =  (len!)/(num[0]! * num[1]! * ... * num[25]!)  MOD 1e9+7;

根据这个公式我们只需要求一下阶乘的逆元就行了,因为是取模的运算,所以我们一边乘一边取模,不会超long long,最后不要忘记的是,如果是负数要转化为正数在进行取模,最后就是乘起来就行了。。。

 

My Code:


#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int MAXN = 1e3+5;
char str[MAXN];
int num[28];
LL a[28];
void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>str;
        int len = strlen(str);
        memset(num, 0, sizeof(num));
        for(int i=0; i<len; i++)
            num[str[i]-'a']++;
        int sum = 0;
        for(int i=0; i<26; i++)
            if(num[i]%2)
                sum++;
        if(sum >= 2)
            puts("0");
        else
        {
            LL ret = 1;
            len>>=1;
            for(int i=0; i<26; i++)
            {
                LL x, y;
                num[i]>>=1;
                a[i] = 1;
                for(int j=1; j<=num[i]; j++)
                    a[i] = a[i]*j%MOD;
                Ex_gcd(a[i], MOD, x, y);
                x = (x%MOD+MOD)%MOD;
                a[i] = x;
            }
            for(int i=1; i<=len; i++)
                ret = ret*i%MOD;
            for(int i=0; i<26; i++)
                ret = ret*a[i]%MOD;
            printf("%lld\n",ret%MOD);
        }   
    }
    return 0;
}


目录
相关文章
|
网络协议 算法 定位技术
利用GPS北斗卫星系统开发NTP网络时间服务器
利用GPS北斗卫星系统开发NTP网络时间服务器
|
Shell 测试技术 Linux
通过shell脚本进行linux服务器的CPU和内存压测
通过shell脚本进行linux服务器的CPU和内存压测
968 0
|
Linux API 数据安全/隐私保护
|
5月前
|
消息中间件 数据挖掘 API
矩阵系统Python实战:零基础搭建抖音小店多店铺自动化运营体系
本文基于抖音开放平台官方接口,详解矩阵系统的技术架构与落地方法,针对抖音小店多店铺运营的效率痛点,面向零基础读者拆解系统分层设计,覆盖身份认证管理、商品库存同步、订单聚合处理、客服自动回复、运营数据分析、合规风控检测六大核心模块。全文附带完整可运行的Python代码,提供轻量化本地部署方案,无需复杂服务环境即可快速搭建,帮助开发者与商家实现多店铺统一管理,降低重复运营成本。
|
域名解析 缓存 监控
阿里云渠道商:如何排查阿里云CDN访问问题?
排查阿里云CDN访问问题需分步诊断:先检查DNS解析与CDN基础配置,再根据访问慢、内容未更新或50x错误等现象定位原因,结合ping、tracert及阿里云实时日志、节点检测等工具深度分析。掌握此流程,快速解决异常。
|
9月前
|
编解码 监控 测试技术
FurMark_2.9.0.0_Win64安装步骤详解(附显卡烤机与温度测试教程)
FurMark 2.9.0.0 Win64 是专业显卡压力测试工具,用于满载烤机、检测温度与稳定性。支持实时监控FPS/温度/功耗,操作简单:管理员运行安装包→自定义路径→创建桌面快捷方式→启动后选择分辨率与AA即可开始测试,适合游戏玩家与硬件爱好者。(239字)
|
11月前
|
人工智能
# 用Prompt Engineering高效生成合规Amazon包类套图
利用Prompt Engineering,仅需1张实拍图+产品参数,即可高效生成符合Amazon美国站合规要求的包类套图。通过结构化提示词,明确主图、卖点、场景等6类图片职责,确保每张图精准传达信息,避免AI篡改产品细节,实现低成本、可复用、规模化出图,大幅提升上架效率。
|
11月前
|
监控 数据可视化 调度
向阳水库智慧监测大屏:Axure大屏可视化原型设计案例
向阳水库智慧监测大屏是基于Axure的可视化原型,采用深蓝科技风设计,集成实时数据、调度方案、智能控制与趋势图表,实现水库运行的高效监控与智能管理。(238字)
548 0
|
机器学习/深度学习 人工智能 算法
大型语言模型为何产生幻觉
语言模型为何会产生幻觉?OpenAI 最新研究指出,幻觉源于模型在训练和评估中被鼓励猜测而非承认“不知道”。即使强大如 GPT-5,也无法完全避免幻觉。改进评估方式、奖励模型表达不确定性,是减少幻觉的关键。
852 10
|
JSON 移动开发 网络协议
gRPC不是银弹:为内网极致性能,如何设计自己的RPC协议?
自研RPC协议针对内网高并发场景,通过精简帧头、长度前缀解决TCP拆包粘包,支持灵活扩展与高效序列化,显著提升性能与资源利用率,适用于对延迟敏感的分布式系统。
705 4