17

HDU5651 xiaoxin juju needs help（逆元）

 3 years ago
source link: https://arminli.com/hdu5651/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

HDU5651 xiaoxin juju needs help（逆元）

March 27, 2016

题目链接

题意：随意打乱顺序，求能构成回文串的个数。

判断一下能计算的条件，方法是 strlen(l)/2 的阶乘除以每个字母出现次数一半的阶乘的积。

逆元：在 MOD 的情况下， （a/b ) %MOD 不能直接 / b 来求，需要找到一个数 inv 使得 inv * b % MOD = 1 。 这样 (a / b) % MOD = (a * inv) % MOD;

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const long long mod = 1e9+7;
long long a[1005];
int cnt[30];
void init(){
    a[0] = 1;
    a[1] = 1;
    for(int i = 2; i <= 1000; i++)
        a[i] = (i*a[i-1])%mod;
}
long long quickmod(long long a, long long n){
    long long r = 1;
    while(n){
        if(n&1){
            r = (a*r)%mod;
        }
        a = (a*a)%mod;
        n >>= 1;
    }
    return r;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n; cin >> n;
    init();
    while(n--){
//        v.clear();
        char s[1005];
        scanf("%s", s);
        memset(cnt, 0, sizeof(cnt));
        int l = strlen(s);
        for(int i = 0; i < l; i++){
            cnt[s[i]-'a']++;
        }
        int k = 0;
        for(int i = 0; i < 26; i++){
            if(cnt[i]%2) k++;
        }
        if(l==1) cout << "1" << endl;
        else if((k==1 && l%2==1) || (l%2==0 && k==0)){
            long long ans = a[l/2];
            //cout << ans << endl;
            for(int i = 0; i < 26; i++){
                ans = (ans*quickmod(a[cnt[i]/2], mod-2))%mod;
                //cout << ans << endl;
            }

            cout << ans << endl;
        }else{
            cout << "0" << endl;
        }
    }
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK