hdu5651 xiaoxin juju needs help (多重集的全排列+逆元)
题意:给你一个字符串,求打乱字符后,有多少种回文串。 (题于文末)
知识点:
n个元素,其中a1,a2,····,an互不相同,进行全排列,可得n!个不同的排列。
若其中某一元素ai重复了ni次,全排列出来必有重复元素,其中真正不同的排列数应为 ,即其重复度为ni!
同理a1重复了n1次,a2重复了n2次,····,ak重复了nk次,n1+n2+····+nk=n。
对于这样的n个元素进行全排列,可得不同排列的个数实际上是
题解:
字符串长度为len,若每个元素的重复次数ni为奇数的个数count>1,则无法形成回文串。
当能构成回文串时,我们只需考虑这个回文串左半部分的情况,所以这个问题也就变成了求一半字符串的有重复的全排列。
因为涉及到除法取模的问题,所以用到逆元。
逆元可以用扩展欧几里得,或费马小定理。/*6.逆元*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
int cnt[260];
char ch[1005]; LL jiecheng(int n)
{
if(n==0)
return 1;
LL ans=1;
for(int i=1;i<=n;i++)
ans=ans*i%MOD;
return ans;
} LL x,y;
LL gcd(LL a,LL b)
{
LL t,d;
if(b==0)
{
x=1,y=0;
return a;
}
d=gcd(b,a%b);
t=x, x=y, y=t-(a/b)*y;
return d;
} int main()
{
int t;
cin>>t;
while(t--)
{
memset(cnt,0,sizeof(cnt));
scanf("%s",ch);
int len=strlen(ch);
for(int i=0;i<len;i++)
{
cnt[ch[i]-' ']++;
}
int count=0;
for(int i=0;i<260;i++)
{
if(cnt[i]&1)
count++;
cnt[i]/=2;
}
if(count>1)
{
cout<<0<<endl;
continue;
}
LL ans=jiecheng(len/2)%MOD;
for(int i=0;i<260;i++)
{
if(cnt[i]>0)
{
gcd(jiecheng(cnt[i]),MOD);
if(x<0)
x+=MOD;
ans=ans*x%MOD;
}
}
cout<<ans<<endl;
}
}
xiaoxin juju needs help
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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\leq 20)$ which represents the number of test cases.
For each test case, there is a single line containing a string $S(1 \leq length(S) \leq 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
最新文章
- Oracle常用函数汇总
- devenv.exe assert failure
- 火车头wordpress免费万能发布模块和接口
- PHP的学习--可变变量
- 孟加拉央行SWIFT攻击事件恶意木马分析(转)
- hadoop错误DataXceiver error processing WRITE_BLOCK operation
- PHP - Windows安装Pear
- Apache HTTP Server 与 Tomcat 的三种连接方式介绍(转)
- 使用JS通过正则限制input的输入
- Setup a private http/nginx based GIT server
- 将Excle中的数据批量导入数据库
- mongodb相关 (population)
- 【HNOI 2017】大佬
- OTP&;ETS
- python unittest装载、执行、造成报告
- day 10 函数入门
- vue moment库格式化处理后端传的日期
- 分布式监控系统Zabbix-3.0.3-完整安装记录 - 添加shell脚本监控
- Ajax jquery的库的简化版本
- Linux中Redis的安装
热门文章
- 【Oracle 集群】Linux下Oracle RAC集群搭建之基本测试与使用(九)
- Oracle迁移:Linux->;Windows
- express路由探析(续)
- SqlDateTime overflow. Must be between 1/1/1753 12:00:00 AM and 12/31/9999 11:59:59 PM.
- 【转译】加入ZigBee联盟,共画物联网的未来
- Java 单例模式详解
- Java-加载数据库驱动,取得数据库连接
- java多线程同步,等待,唤醒
- 浏览器对localstorage的支持情况以及localstorage在saas系统中的应用实践思考
- linux(十一)__Apache服务器