結果
問題 |
No.171 スワップ文字列(Med)
|
ユーザー |
![]() |
提出日時 | 2015-07-09 07:12:38 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 1,000 ms |
コード長 | 1,563 bytes |
コンパイル時間 | 845 ms |
コンパイル使用メモリ | 88,672 KB |
実行使用メモリ | 7,336 KB |
最終ジャッジ日時 | 2024-07-08 01:46:25 |
合計ジャッジ時間 | 1,381 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <array> #include <list> #include <queue> #include <vector> #include <complex> #include <set> ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)<<endl; ///////// typedef long long LL; typedef long double LD; ///////// using namespace::std; ///////// const LL mod = 573; LL cdp[1001][501]; LL ccc(int n,int k){ if(k<0){ return 0; } else if( n < k){ return 0; } //0<=k<=n k = min(k,n-k); if(k==0){ return 1; } else if( k == 1){ return n; } else if( cdp[n][k] != -1){//[0,mod-1]が入る,未使用判定なら範囲外の値が必要 return cdp[n][k]; } //////// LL ans = 0; ans = ( ccc(n-1,k-1) + ccc(n-1,k) )%mod; cdp[n][k] = ans; return ans; } void initCdp(int n){ for(int i=0;i<=n/2;++i){ for(int k=0; k+k <= i;++k){ //cout << "["<<i<<","<<k<<"] "; ccc(i,k); } } return; } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// cout << setprecision(10);// string str; cin>>str; int N = str.size(); int s[26]; rep(i,26)s[i]=0; rep(i,N){ ++s[ str[i] - 'A' ]; } sort(s,s+26); /////////////// rep(i,1001)rep(j,501) cdp[i][j] = -1; //initCdp(N); //cout<< "End init" << endl; /////////////// LL ans=1; int nokori = N; rep(i,26){ ans *= ccc( nokori,s[i] ); ans %= mod;//mod nokori -= s[i]; } if( ans == 0){ ans = mod; } P(ans-1); return 0; }