結果
問題 | No.171 スワップ文字列(Med) |
ユーザー |
|
提出日時 | 2015-02-22 09:40:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 1,011 bytes |
コンパイル時間 | 1,381 ms |
コンパイル使用メモリ | 165,068 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 21:49:19 |
合計ジャッジ時間 | 1,990 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
// 想定解: 組み合わせ// 事前計算O(max(|S|)^2) 入力処理O(|S|+T), T=文字の種類(26)#include <bits/stdc++.h>using namespace std;template<typename _T> void rc(_T v,_T mn,_T mx){if(v<mn||mx<v){cerr<<"error"<<endl;throw;}}const int MOD = 573;// nCm MODint combination_mod(int n, int m){static vector<vector<int> >c;static int maxn;if(n<0||m<0||n<m)return 0;m=min(m,n-m);if(n>maxn){c.resize(n+1);for(int i=maxn;i<=n;i++)c[i].resize(i+1);c[0][0]=1;for(int i=maxn+1;i<=n;i++){for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;c[i][0]=c[i][i]=1;}maxn=n;}return c[n][m];}int s[256];int main(){string S; cin >> S;rc((int)S.size(), 1, 1000);for(const auto &c : S) rc(c, 'A', 'Z');for(const auto &c : S) s[c]++;int n = S.size();int res = 1;for(int i = 'A'; i <= 'Z'; i++){(res *= combination_mod(n, s[i])) %= MOD;n -= s[i];}// (res-1) % MOD(res += MOD-1) %= MOD;cout << res << endl;}