結果

問題 No.171 スワップ文字列(Med)
コンテスト
ユーザー ayame_py
提出日時 2016-02-10 15:32:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,285 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 166,604 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-21 22:05:47
合計ジャッジ時間 1,831 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

//エラトステネスの篩
void eratosthenes(int num, map<int,int> &prime){
    for(int i = 2; i * i <= num; i++){
        while(num%i==0){
            prime[i]++;
            num/=i;
        }
    }
    if(num!=1) prime[num]++;
}

ll mod_pow(ll n, ll m){
    if (m==0) return 0;
    if (m==1) return n;
    ll tmp = mod_pow(n,m/2);
    tmp*=tmp;
    tmp%=573;
    if (m%2==0) return tmp;
    tmp*=n;
    tmp%=573;
    return tmp;
}

string s;
int alpha[26];

int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    REP(i,s.length()) alpha[s[i]-'A']++;
    map<int,int> numerator;
    map<int,int> denominator;
    FOR(i,2,s.length()+1)eratosthenes(i, numerator);
    REP(i,26)FOR(j,2,alpha[i]+1)eratosthenes(j,denominator);
    ll ans=1;
    for(auto x: numerator){
        int a = numerator[x.first]-denominator[x.first];
        if(a!=0) ans*=mod_pow(x.first,a);
        ans%=573;
    }
    ans+=572;
    ans%=573;
    cout << ans << endl;
    return 0;
}
0