HDU 5651 xiaoxin juju needs help 数学

HDU 5651 xiaoxin juju needs help 数学


xiaoxin juju needs help

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=5651

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

Hint

题意

给你一个串,你可以改变字符位置

问你能够形成多少种回文串。

题解:

首先把答案为0的情况判断掉

然后就很简单了,因为回文嘛,所以左右肯定相同

然后就可以排列组合怼一波了

就相当于选位置,把所有字母安上去。

C(x1,x2)*C(y1,y2)….这种

代码

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e5+7;
int num[30];
typedef long long ll;
ll fac[maxn];
ll qpow(ll a,ll b)
{
    ll ans=1;a%=mod;
    for(ll i=b;i;i>>=1,a=a*a%mod)
        if(i&1)ans=ans*a%mod;
    return ans;
}
ll C(ll n,ll m)
{
    if(m>n||m<0)return 0;
    ll s1=fac[n],s2=fac[n-m]*fac[m]%mod;
    return s1*qpow(s2,mod-2)%mod;
}
void solve()
{
    memset(num,0,sizeof(num));
    string s;cin>>s;
    for(int i=0;i<s.size();i++)
        num[s[i]-'a']++;
    if(s.size()%2==0)
    {
        for(int i=0;i<26;i++)
            if(num[i]%2==1)
            {
                printf("0\n");
                return;
            }
    }
    else
    {
        int cnt = 0;
        for(int i=0;i<26;i++)
            if(num[i]%2==1)cnt++;
        if(cnt!=1)
        {
            printf("0\n");
            return;
        }
    }
    long long ans = 1;
    long long las = s.size();
    for(int i=0;i<26;i++)
    {
        ans = (ans * C(las/2,num[i]/2))%mod;
        las-=num[i];
    }
    printf("%lld\n",ans);
}
int main()
{
    fac[0]=1;
    for(int i=1;i<maxn;i++)
        fac[i]=fac[i-1]*i%mod;
    int t;scanf("%d",&t);
    while(t--)solve();
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 有监督学习、无监督学习以及半监督学习详解

    有监督学习、无监督学习以及半监督学习详解相信大家在开始学习机器学习的入门时,首先接触的概念就是监督学习、无监督学习以及半监督学习。在我们开始讲解之前,我们先回顾一下什么是机器学习(ML)?百度百科给出的定义是,机器学习是一门多学科交叉专业,涵盖概率论知识,统计学知识,近似理论知识和复杂算法知识,使用计算机作为工具并致力于真实实时的模拟人类学习方式,并将现有内容进行知识结构划分来有效提高学习效率。从定义中,我们可以发现:(1)机器学习是一门人工智能的科学,该领域的主要研究对象是人工智能,特别是如何在经验学习中改善具体算法…

  • virsh 命令_vim命令

    virsh 命令_vim命令下文domain表示虚拟机名字或id或uuid 1.列出虚拟机的所有网口:virshdomiflistdomain结果如下:Interface Type      Source    Model      MAC——————————————————-vnet0     bridge    br0     v…

  • Angular 2 前端 http 传输 model 对象及其外键的问题

    Angular 2 前端 http 传输 model 对象及其外键的问题

    2021年11月24日
  • 触摸事件 touchstart、touchmove、touchend

    触摸事件 touchstart、touchmove、touchend目录触摸事件触摸事件编码触摸手指个数分析触摸目标DOM元素分析触摸位置分析触摸事件HTML5中,PC端基于鼠标的界面互动主要是单击,移动端界面交互方式主要是触摸。移动端浏览器触摸事件事件名称 描述 是否包含touches数组 touchstart 触摸开始,多点触控,后面的手指同样会触发 是 touchmove …

  • 使用navicat 链接数据库时乱码

    使用navicat 链接数据库时乱码

  • input debounce

    input debounce项目背景是一个搜索框,不能实时的监听onChange事件去发送请求,这样会造成服务器的压力解决思路就是用setTimeout+clearTimeout普通js代码如下:/下面是普通的js实现,可以参考一下//获取input元素vartextInput=document.getElementById(‘test-input’);//初始化一个…

发表回复

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

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