yukicoder No.171 スワップ文字列(Med)
これわからなかったのちょっと恥ずかしい気がする
問題:http://yukicoder.me/problems/414
解法:573が素数じゃないので、割り算するのはマズイ。ということで、数え上げをすべて掛け算で済ませることを考える。M個の数列でm1,m2,m3,...,mn個の共通因子がある場合の場合の数は、となるので、コンビネーションを予めdpでメモしておけば掛け算のみの演算で解くことができる。
以下ソースコード
const ll MOD = 573; const int MAXN = 1024; ll cmb[MAXN][MAXN]; void init() { cmb[0][0] = 1; for (int i = 1; i < MAXN; i++) { cmb[i][0] = 1; for (int j = 1; j <= i; j++) { cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1]) % MOD; } } } int main() { init(); string s; cin >> s; int n = s.size(); map<char, int> m; for (char c : s) { m[c]++; } ll ans = 1; for (auto el : m) { ans *= cmb[n][el.second]; n -= el.second; ans %= MOD; } cout << (ans-1+MOD)%MOD << endl; return 0; }