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)


相关推荐

  • 零基础学Java(3)运算符[通俗易懂]

    零基础学Java(3)运算符[通俗易懂]运算符运算符用于连接值。Java提供了一组丰富的算术和逻辑运算符以及数学函数。算术运算符在Java中,使用算术运算符+、-、*、/表示加、减、乘、除运算。当参与/运算的两个操作数都是整数时,表示

  • eclipse怎样导入java项目

    eclipse怎样导入java项目打开eclipse,点击file,点击import选择ExistingProjectsintoWorkspace,点击next点击Browse然后选择项目所在的文件夹最后点击Finish导入完成

  • 系统错误号:0x8007005[通俗易懂]

    系统错误号:0x8007005通常这个错误代码是错误的权限导致的,所以只要改变系统的安全设置就行了。下载这个文件SubInACL(SubInACL.exe)http://www.microsoft.com/downloads/details.aspx?FamilyID=e8ba3e56-d8fe-4a91-93cf-ed6985e3927b&displaylang=en安装这

  • latex大的中括号_文献引用中括号怎么标注

    latex大的中括号_文献引用中括号怎么标注括号是数学中最常用的符号之一。括号不仅能使我们的公式更加美观,还能使我们的表达更为清晰、丰富。latex里面的括号和我们常见的括号是一样的,主要是小括号、中括号(或者叫方括号)和花括号。这里我们看到花括号如果直接打出来的话是不显示任何东西的,这里我们需要加一个转义符,也就是反斜杠。如果只用直接的括号字符,只能打出固定大小的括号,比如这样打出的括号就比较小。那么如何打出更大一点的括号呢?在latex…

    2022年10月10日
  • django验证码登录_双重认证怎么关闭

    django验证码登录_双重认证怎么关闭djoser是什么?作用:Django认证系统的REST实现。djoser库提供了一组DjangoRestFramework视图,用于处理注册、登录、注销、密码重置和帐户激活等基本操作。它适用于

  • jquery弹窗插件dialog_jquery进度条插件

    jquery弹窗插件dialog_jquery进度条插件143行js顶部进度条最小插件-nanobar.js源码解析

发表回复

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

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