HDU xiaoxin jujuju needs help(역 원+배열 조합)
제목:http://acm.hdu.edu.cn/showproblem.php?pid=5651
제목:몇 개의 소문 자로 구 성 된 문자열 을 유전 합 니 다.서로 자 리 를 임의로 바 꿀 수 있 지만 요 소 를 삭제 하거나 추가 할 수 없습니다.몇 가지 서로 다른 답장 문자열 을 구성 할 수 있 는 지 물 어보 세 요.사고방식:아주 간단 한 배열 조합 이다.너무 간단 하면 나 는 그 를 배열 조합 에 나 누 지 않 을 것 이다.먼저 회 문 열 을 구성 할 수 있 는 지 여 부 를 판단 하고,한 개 이상 의 홀수 가 같은 자모 가 있다 면 어떻게 든 회 문 열 을 구성 하지 않 을 것 이다.나머지 는 문자열 의 한 쪽 을 매 거 하고 모든 요 소 를 반 으로 취한 다.모든 원소 의 절반 과 곱 하기 가 모든 원소 의 절반 을 나 누 는 곱 하기 가 답 이다.이것 이 바로 문제 의 소재 이 며,그 다음 을 제외 하고 모형 을 뽑 아야 한다.제법 취 모 문 제 는 당연히 역 원 이지,역 원 에 대해 서 는 당연히 페 마 의 작은 정리 지.페 르 마 소정 리:페 르 마 소정 리(Fermat Theory)는 수론 중의 중요 한 정리 이다.그 내용 은 p 가 질 수 이 고(a,p)=1 이 라면 a(p-1)1.1(mod p)이다.즉,a 가 정수 이 고 p 가 질 수 이 며 a,p 의 상호 질(즉 둘 은 하나의 공약수 1 만 있 음)이 라면 a 의(p-1)차방 은 p 의 나머지 를 1 로 나 누 는 것 이다.
#include<stdio.h>
#include<string.h>
const int maxn=1111;
int num[maxn];
char s[maxn];
typedef long long ll;
const int mod=1e9+7;
ll f[maxn];
void init()
{
f[0]=1;
f[1]=1;
for(int i=2;i<maxn;i++)
f[i]=f[i-1]*i%mod;
}
ll cal(ll x)
{
ll res=1;
int k=mod-2;
while(k)
{
if(k&1)
{
res*=x;
res%=mod;
}
x*=x;
x%=mod;
k>>=1;
}
return res;
}
int main()
{
int T;
init();
while(scanf("%d",&T)!=EOF)
while(T--)
{
scanf("%s",s);
int n=strlen(s);
memset(num,0,sizeof(num));
for(int i=0;i<n;i++)
num[s[i]-'a']++;
int len=0;
for(int i=0;i<26;i++)
if(num[i]%2)
len++;
if(len>1)
{
printf("0
");
continue;
}
int total=0;
for(int i=0;i<26;i++)
{
num[i]/=2;
total+=num[i];
}
ll res=f[total];
for(int i=0;i<26;i++)
if(num[i])
{
res=res*cal(f[num[i]])%mod;
}
printf("%lld
",res);
}
return 0;
} too difficult！！！！
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
