abc 110 D 整数 二項係数

C

必要十分条件は、S中の同じ文字がT中の異なる文字に対応しない。かつT中の同じ文字がS中の異なる文字に対応しないこと。

# include<iostream>
# include<algorithm>
# include<vector>
# include<string>
# include<list>
# include<cmath>
# include<map>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main() {
	string S, T;
	cin >> S >> T;
	bool ok = true;
	map<char, char>ma, ima;
	for (int i = 0; i < S.size(); ++i) {
		char s = S[i], t = T[i];
		if (ma.count(s))if (ma[s] != t)ok = false;
		if (ima.count(t))if (ima[t] != s)ok = false;
		ma[s] = t; ima[t] = s;
	}
	if (ok)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

D
整数N,Mが与えられる。
a1a2.....aN=Mを満たす整数の組(a1,a2,,,,aN)が何通りあるか,1000000007で割った余りを求めよ。
まずは素数べきで考えるというのが１つの定石ではある。pを素数として
a1a2,,,,*aN=pk
を満たす(a1,a2,,,,aN)が何通りあるかを考える。これは実はpの指数に着目してai=pxiとしてx1+x2+,,,+xN=kを満たす0以上の整数が何通りあるかを数え上げる問題と考えることができる
これを各素因子ごとに独立に行って得られた結果を掛け算していけばよい

# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 7;
vector<pair<ll, ll>>prime_factorize(ll n) {
	vector<pair<ll, ll>>res;
	for (ll p = 2; p*p <= n; ++p) {
		if (n%p != 0)continue;
		int num = 0;
		while (n%p == 0) { ++num; n /= p; }
		res.push_back(make_pair(p, num));
	}
	if (n != 1)res.push_back(make_pair(n, 1));
	return res;
}
const int MAX = 210000;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}
ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
int main() {
	int N, M;
	COMinit();
	cin >> N >> M;
	auto vec = prime_factorize(M);
	ll res = 1;
	for (auto pa : vec) {
		int num = pa.second;
		ll tmp = COM(num + N - 1, N - 1);
		res = (res*tmp) % INF;
	}
	cout << res << endl;
	return 0;
}

二項係数について

# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 7;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}

int main() {
	COMinit();//前処理
	cout << COM(100000, 50000) << endl;//計算例
}

使用可能場面1<=k<=n<=10**7
使用原理
nCk=(n!)(k!)^(-1)((n-k)!)^(-1)

COMinit()でa!(fac[a])と(a!)^(-1)(finv[a])のテーブルを予め作っている。

Euclidの互除法による逆元計算
a^(-1)mod pを計算するとはすなわち
ax+py=1
を満たすxを求めたいということになる。Euclidの互除法を利用する。すなわちpをaで割ってみる。
p=qa+r
これを代入すると
ax+(qa+r)y=1<=>ry+a(x+qy)=1
になる。これによって(a,p)に関する問題がそれより数値の小さな(r,a)に関する問題に帰着できた。これを再帰的に解くのが拡張Euclidの互除法です。具体的には(r,a)に関する小問題を解いてrs+at=1と解(s,t)が再帰的に得られたとすると、y=s,x+qy=t<=>x=t-q*s,y=s
という風に元の問題の解を構成できます