조합 수학 학습 (1) - 배열 조합과 모함수 고전 연습 문제
32229 단어 활용단어참조
inline void read(int &x){
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && !isdigit(ch))
ch = getchar();
if(ch == '-')
w = -1, ch = getchar();
while(isdigit(ch))
data = 10 * data + ch - '0', ch = getchar();
x = data * w;
}
void write(int x){
if(x < 0)
putchar('-'), x = -x;
if(x > 9)
write(x / 10);
putchar('0' + x % 10);
}
const int maxn = 1024 + 5;
int n, m, a[maxn];
int main()
{
int t; read(t);
while (t--) {
read(n), read(m);
for (int i = 1; i <= n; ++i) read(a[i]);
while (m) { next_permutation(a + 1, a + n + 1); m--; }
for (int i = 1; i <= n; ++i) {
write(a[i]);
putchar(i == n ? '
' : ' ');
}
}
}
C - Round Numbers는 바이너리 구간에서 0의 수량이 1의 수량보다 많은 십진수의 개수 dp를 구하고 0과 1의 수량차를 하나의 변수로 저장한다. 중간에 0보다 작은 수량이 나타날 수 있기 때문에 우리는 32를 더하여 0보다 크게 하면 된다.
const int maxn = 32 + 5;
int dp[maxn][maxn << 1], a[maxn];
int f(int pos, int num, bool limit, bool lead) {
if (pos == -1) return num >= 0;
if (!limit && !lead && dp[pos][num + maxn] != -1) return dp[pos][num + maxn];
int up = limit ? a[pos] : 1, sum = 0;
for (int i = 0; i <= up; ++i) {
if (lead && i == 0) sum += f(pos - 1, num, limit && i == a[pos], lead && i == 0);
else sum += f(pos - 1, num + (i == 0 ? 1 : -1), limit && i == a[pos], lead && i == 0);
}
if (!limit && !lead) dp[pos][num + maxn] = sum;
return sum;
}
int solve(int x) {
int p = 0;
while (x) {
a[p++] = x % 2;
x /= 2;
}
return f(p - 1, 0, true, true);
}
int main()
{
memset(dp, -1, sizeof(dp));
int a, b; read(a), read(b);
write(solve(b) - solve(a - 1));
putchar('
');
}
D - 오름차순과 주어진 문자열의 수량보다 작은 숫자 dp를 구하고 현재 선택한 문자를 변수로 저장합니다
char str[12];
ll dp[12][30];
ll f(int pos, int ch, bool limit, bool lead) {
//printf("pos = %d, ch = %d, limit = %d
", pos, ch, limit);
if (pos == -1) return ch > 0;
if (!limit && dp[pos][ch] != -1) return dp[pos][ch];
int up = limit ? str[pos] - 'a' + 1 : 26; ll sum = 0;
//printf("%d-%d
", limit, up);
for (int i = lead ? 0 : ch + 1; i <= up; ++i) {
sum += f(pos - 1, i, limit && i == up, lead && i == 0);
}
if (!limit) dp[pos][ch] = sum;
return sum;
}
int main()
{
memset(dp, -1, sizeof(dp));
while (~scanf("%s", &str)) {
int n = strlen(str);
bool flg = true;
for (int i = 1; i < n; ++i) {
if (str[i] <= str[i - 1]) {
flg = false;
break;
}
}
if (!flg) { printf("0
"); continue; }
reverse(str, str + n);
printf("%lld
", f(n - 1, 0, true, true));
}
}
E-Number Sequence는 먼저 규칙을 찾아 1∼9 1\sim 9 1∼9 사이 매 길이에 1을, 10∼99 10\sim 99 10∼99 사이 매 길이에 2100∼999 100\sim 999 100∼999 사이 매번 3을 더해 차례로 유추하는 것을 발견했다.숫자의 범위는 9에서 90에서 900..., 공차는 1에서 2에서 3까지...주어진 범위 내의 공차가 최대 5까지 되는 것을 발견하면, 우리는 폭력적으로 매 수의 공차의 큰 범위를 찾아 다시 2분 동안 구체적인 숫자를 찾는다
int main()
{
int t; scanf("%d", &t);
while (t--) {
ll k; scanf("%lld", &k);
int d = 0, a1 = 0, sz = 9;
ll sum = 0;
while (true) {
d++; a1 += d;
ll tmp = 1ll * a1 * sz + 1ll * sz * (sz - 1) / 2 * d;
if (sum + tmp < k) {
sum += tmp;
a1 = a1 + (sz - 1) * d; sz *= 10;
continue;
}
int l = 0, r = 1e6;
while (l != r) {
int n = (l + r) >> 1;
if (1ll * a1 * n + 1ll * n * (n - 1) / 2 * d >= k - sum) r = n;
else l = n + 1;
}
ll pre = 1ll * a1 * (l - 1) + 1ll * (l - 1) * (l - 2) / 2 * d;
sum += pre;
k = k - sum;
int cnt = 0;
for (int i = 1; ; ++i) {
if (1 <= i && i <= 9) cnt++;
else if (10 <= i && i <= 99) cnt += 2;
else if (100 <= i && i <= 999) cnt += 3;
else if (1000 <= i && i <= 9999) cnt += 4;
else if (10000 <= i && i <= 99999) cnt += 5;
if (cnt >= k) {
cnt -= k;
while (i) {
if (cnt == 0) {
write(i % 10); putchar('
');
break;
}
cnt--;
i /= 10;
}
break;
}
}
break;
}
}
}
F - Paths on a Grid 클래식 배열 조합, 스키마 수 (n + m) {n+m\choose m} (mn+m)
int main()
{
ll n, m;
while (~scanf("%lld%lld", &n, &m)) {
if (n == 0 && m == 0) break;
if (n > m) swap(n, m);
double den = 1, mol = 1;
for (ll i = m + 1; i <= n + m; ++i) {
den *= 1.0 * i;
mol *= 1.0 * (i - m);
}
printf("%.0f
", den / mol);
}
}
G - Word Index D - 네, 같은 문제.
char str[12];
ll dp[12][30];
ll f(int pos, int ch, bool limit, bool lead) {
//printf("pos = %d, ch = %d, limit = %d
", pos, ch, limit);
if (pos == -1) return ch > 0;
if (!limit && dp[pos][ch] != -1) return dp[pos][ch];
int up = limit ? str[pos] - 'a' + 1 : 26; ll sum = 0;
//printf("%d-%d
", limit, up);
for (int i = lead ? 0 : ch + 1; i <= up; ++i) {
sum += f(pos - 1, i, limit && i == up, lead && i == 0);
}
if (!limit) dp[pos][ch] = sum;
return sum;
}
int main()
{
memset(dp, -1, sizeof(dp));
while (~scanf("%s", &str)) {
int n = strlen(str);
bool flg = true;
for (int i = 1; i < n; ++i) {
if (str[i] <= str[i - 1]) {
flg = false;
break;
}
}
if (!flg) { printf("0
"); continue; }
reverse(str, str + n);
printf("%lld
", f(n - 1, 0, true, true));
}
}
H - The Last Non-zero Digit 구급승의 마지막 비0수 참조 수학 관련
int get_prime_factor(int n, int x) {
if (!n) return 0;
return n / x + get_prime_factor(n / x, x);
}
int g(int n, int x) {
if (!n) return 0;
return n / 10 + (n % 10 >= x) + g(n / 5, x);
}
int f(int n, int x) {
if (!n) return 0;
return f(n / 2, x) + g(n, x);
}
//2,3,7,9 ， 2 0 1
int cyclic_section[][4] = {{6, 2, 4, 8}, {1, 3, 9, 7}, {1, 7, 9, 3}, {1, 9, 1, 9}};
int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
int cnt2 = get_prime_factor(n, 2) - get_prime_factor(n - m, 2);
int cnt5 = get_prime_factor(n, 5) - get_prime_factor(n - m, 5);
int cnt3 = f(n, 3) - f(n - m, 3);
int cnt7 = f(n, 7) - f(n - m, 7);
int cnt9 = f(n, 9) - f(n - m, 9);
int ans = 1;
if (cnt5 > cnt2) {
printf("5
"); continue;
}
if (cnt2 != cnt5) {
ans *= cyclic_section[0][(cnt2 - cnt5) % 4];
ans %= 10;
}
ans *= cyclic_section[1][cnt3 % 4]; ans %= 10;
ans *= cyclic_section[2][cnt7 % 4]; ans %= 10;
ans *= cyclic_section[3][cnt9 % 4]; ans %= 10;
printf("%d
", ans);
}
}
I - Hexadecimal Numbers는 이미 선택한 문자를 선택할 수 없으며, 나머지 n n n 문자는 m m을 선택하여 배열하는 시나리오 수는 A n m An^m Anm 각 위치는 선택할 수 있는 알파벳에서 큰 알파벳에서 작은 알파벳으로 판단하고 없으면 0 을 선택합니다
int vis[20], ans[20];
ll c[20][10], fib[10];
int main()
{
for (int i = 1; i <= 16; ++i) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
fib[0] = 1; for (int i = 1; i <= 7; ++i) fib[i] = fib[i - 1] * i;
ll k;
while (~scanf("%lld", &k)) {
int cnt = 0;
bool lead = true;
for (int i = 8, j; i > 0; --i) {
for (j = 15; j >= 1; --j) {
if (vis[j]) continue;
ll tmp = c[16 - cnt - 1][i - 1] * fib[i - 1];
if (tmp < k) k -= tmp;
else { vis[j] = true; break; }
}
if (!lead || j != 0) cnt++;
if (j != 0) lead = false;
if (j == 0 && lead) continue;
printf("%c", j >= 10 ? j - 10 + 'A' : j + '0');
}
putchar('
');
}
}
J - The Counting Problem 계산 범위 내 각 수에 나타나는 개수는 우리가 각 위치를 열거한다. 이 위치는 세 부분으로 나뉘는데 왼쪽의 수는 l e f t left left이고 이 숫자는 n u m num num이며 오른쪽의 수는 r i g h t right right이며 현재 위치의 수는 i i i 이다
c n t = { { l e f t × 1 0 l e n + r i g h t + 1 , i = = n u m l e f t × 1 0 l e n + 1 0 l e n , n u m > i , i ≠ 0 { ( l e f t − 1 ) × 1 0 l e n + r i g h t + 1 , n u m = = i ( l e f t − 1 ) × 1 0 l e n + 1 0 l e n , n u m > i , i = 0 cnt=\begin{cases}\begin{cases}left\times{10^{len}}+right+1,i==num\\left\times10^{len}+10^{len},num>i\end{cases},ie0\\\begin{cases}(left-1)\times10^{len}+right+1,num==i\\(left-1)\times10^{len}+10^{len},num>i\end{cases},i=0\end{cases} cnt=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧{left×10len+right+1,i==numleft×10len+10len,num>i,i=0{(left−1)×10len+right+1,num==i(left−1)×10len+10len,num>i,i=0
int ans[10];
ll fib[10];
int solve(int x, int y) {
int res = 0;
for (int i = 1; i <= 9; ++i) {
int l = x / fib[i - 1];
int r = x - l * fib[i - 1];
int rt = l % 10; l /= 10;
//printf("%d - %d - %d
", l, rt, r);
if (y == 0) {
if (l) {
res += (l - 1) * fib[i - 1];
if (rt == 0) res += r + 1;
else if (rt > y) res += fib[i - 1];
}
}
else {
res += l * fib[i - 1];
if (rt > y) res += fib[i - 1];
else if (rt == y) res += r + 1;
}
if (l <= 0) break;
}
return res;
}
int main()
{
fib[0] = 1; for (int i = 1; i <= 9; ++i) fib[i] = fib[i - 1] * 10;
int a, b;
while (~scanf("%d%d", &a, &b)) {
if (a == 0 && b == 0) break;
if (a > b) swap(a, b);
memset(ans, 0, sizeof(ans));
for (int i = 0; i <= 9; ++i) {
printf("%d%c", solve(b, i) - solve(a - 1, i), i == 9 ? '
' : ' ');
}
}
}
K - How many 0’s? J의 약식 버전
ll fib[12];
ll solve(ll x) {
if (x < 0) return -1;
ll res = 0;
for (int i = 1; i <= 12; ++i) {
ll l = x / fib[i - 1];
ll r = x - l * fib[i - 1];
int rt = l % 10; l /= 10;
if (!l) break;
res += (l - 1) * fib[i - 1];
if (rt) res += fib[i - 1];
else res += r + 1;
}
return res;
}
int main()
{
fib[0] = 1; for (int i = 1; i <= 12; ++i) fib[i] = fib[i - 1] * 10;
ll a, b;
while (~scanf("%lld%lld", &a, &b)) {
if (a == -1 && b == -1) break;
if (a == 0 && b == 0) printf("1
");
else printf("%lld
", solve(b) - solve(a - 1));
}
}
S(0,0)=1 S(0,0)=1 S(0,0)=1 S(0,0)=1 S(0,0)=1, 나머지는 모두 0이므로 정답이 1이면 n=0, m = 0 n=0, m=0n=0, m=0, m=0의 방안 수 S(n,m) = m S(n·m) = m S(n-41,m) + S(n-41 1,m) + S(n-41 1,m -4 S(n,m -1,m) S(n,m) = m(m-1 + S) m(m) m -L - Binary Binary Binary Binary Binary Stirlinlinlinlinlinling Numberss s s s s S(0, L -Bininin L - Binary NumbeS(n -3 1, m -3 1) 패리티 토론
int get(int x) {
int ret = 0;
for (int i = 2; i <= x; i <<= 1) {
ret += x / i;
}
return ret;
}
bool solve(int n, int m) {
return get(n) - get(m) - get(n - m) == 0;
}
int main()
{
int t; read(t);
while (t--) {
int n, m; read(n); read(m);
int decre = n - m, k = (m + 1) / 2;
println(solve(decre + k - 1, k - 1));
}
}
M - Birthday Cake 차이점과 뉴턴 공식 참조 수학 관련
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
Scanner scan = new Scanner(System.in);
BigInteger c[]=new BigInteger[110];
BigInteger h[][] = new BigInteger[110][110];
void getc(BigInteger n, int m) {
c[1] = n;
for (int i = 2; i <= m+1; i++)
c[i] = c[i - 1].multiply(n.subtract(BigInteger.valueOf(i - 1)))
.divide(BigInteger.valueOf(i));
}
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
void run() {
int cas=scan.nextInt();
while(cas-->0){
BigInteger n =scan.nextBigInteger().add(BigInteger.ONE);
int m = scan.nextInt();
for (int i = 0; i <= m; i++)
h[0][i] = BigInteger.valueOf(i).pow(m);
for (int i = 1; i <= m; i++)
for (int j = 0; j <= m - i; j++)
h[i][j] = h[i - 1][j + 1].subtract(h[i - 1][j]);
BigInteger ans = BigInteger.ZERO;
getc(n, m);
for (int i = 0; i <= m; i++)
ans=ans.add(h[i][0].multiply(c[i+1]));
out.println(ans);
out.flush();
}
}
public static void main(String[] args) {
new Main().run();
}
}
N - Sum of powers 버누리 수 해결 등멱구와 참조 수학 관련
typedef long long ll;
const int maxn = 20 + 3;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
ll ret = a / gcd(a, b) * b;
return ret ? ret : -ret;
}
struct fraction {
ll a, b;
fraction() {}
fraction(ll x) { a = x; b = 1; }
fraction(ll x, ll y) { a = x; b = y; }
void deal() {
if (b < 0) b = -b, a = -a;
ll k = gcd(a, b);
if (k < 0) k = -k;
a /= k; b /= k;
}
fraction operator +(const fraction& rhs) const {
fraction ans;
ans.b = lcm(b, rhs.b);
ans.a = ans.b / b * a + ans.b / rhs.b * rhs.a;
ans.deal();
return ans;
}
fraction operator -(const fraction& rhs) const {
fraction ans;
ans.b = lcm(b, rhs.b);
ans.a = ans.b / b * a - ans.b / rhs.b * rhs.a;
ans.deal();
return ans;
}
fraction operator *(const fraction& rhs) const {
fraction ans;
ans.a = a * rhs.a;
ans.b = b * rhs.b;
ans.deal();
return ans;
}
fraction operator /(const fraction& rhs) const {
fraction ans;
ans.a = a * rhs.b;
ans.b = b * rhs.a;
ans.deal();
return ans;
}
void println() {
printf("%lld/%lld
", a, b);
}
};
fraction B[maxn];
ll C[maxn][maxn];
void init() {
for (int i = 1; i < maxn; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
B[0] = fraction(1);
for (int i = 1; i <= 20; ++i) {
B[i] = fraction(0);
for (int j = 0; j < i; ++j)
B[i] = B[i] - fraction(C[i + 1][j]) * B[j];
B[i] = B[i] / fraction(C[i + 1][i]);
}
}
int n; fraction a[maxn];
int main() {
init();
while (~scanf("%d", &n)) {
ll Lcm = 1;
for (int i = 0; i <= n; ++i) {
a[i] = fraction(C[n + 1][i]) * B[i] * fraction(1, n + 1);
Lcm = lcm(Lcm, a[i].b);
}
printf("%lld ", Lcm);
a[1] = a[1] + fraction(1);
for (int i = 0; i <= n; ++i)
printf("%lld ", Lcm / a[i].b * a[i].a);
puts("0");
}
}
O - Ignatius and the Princess III dfs
const int maxn = 120 + 5;
int dp[maxn][maxn];
int solve(int n, int m) {
if (n == 0) return 1;
if (m > n) return 0;
if (dp[n][m] != -1) return dp[n][m];
int res = 0;
for (int i = m; i <= n; ++i) {
if (n - i >= i) {
res += solve(n - i, i);
}
else if (i == n)
res += solve(0, i);
}
return dp[n][m] = res;
}
int main()
{
memset(dp, -1, sizeof(dp));
int n;
while (~scanf("%d", &n)) {
println(solve(n, 1));
}
}
P - Train Problem II 대수 + 카탈란 수 클래식 응용
const int maxn = 100 + 5;
struct Bigint
{
vector s;
Bigint() { s.clear(); }
Bigint operator =(int n) {
while (n) {
s.push_back(n % 10);
n /= 10;
}
return *this;
}
friend Bigint operator *(const Bigint& a, const int& b) {
Bigint res; int k = 0;
for (int i = 0; i < a.s.size(); ++i) {
res.s.push_back((k + a.s[i] * b) % 10);
k = (k + a.s[i] * b) / 10;
}
while (k) {
res.s.push_back(k % 10);
k /= 10;
}
return res;
}
friend Bigint operator /(const Bigint& a, const int& b) {
Bigint res; int k = 0;
for (int i = a.s.size() - 1; i >= 0; --i) {
res.s.push_back((k * 10 + a.s[i]) / b);
k = (k * 10 + a.s[i]) % b;
}
reverse(res.s.begin(), res.s.end());
while (res.s.back() == 0) res.s.pop_back();
return res;
}
void print() {
for (int i = s.size() - 1; i >= 0; --i) {
putchar(s[i] + '0');
}
}
};
Bigint C[maxn];
int main()
{
C[0] = 1;
for (int i = 1; i <= 100; ++i) {
C[i] = C[i - 1] * (4 * i - 2);
C[i] = C[i] / (i + 1);
}
int n; while (~scanf("%d", &n)) {
C[n].print(); putchar('
');
}
}
Q - 배열 조합 지수형 모함수 해석
double fib(int n) {
double res = 1.0;
for (int i = 1; i <= n; ++i) {
res = res * i;
}
return res;
}
double a[maxn], f[maxn], g[maxn];
int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for (int i = 0; i < n; ++i) {
scanf("%lf", &a[i]);
}
for (int i = 0; i <= a[0]; ++i) {
f[i] = 1.0 / fib(i);
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= a[i] && j + k <= m; ++k) {
g[j + k] += f[j] / fib(k);
}
}
for (int j = 0; j <= m; ++j) {
f[j] = g[j]; g[j] = 0;
}
}
printf("%.0lf
", f[m] * fib(m));
}
}
S - 팩트스톤 벤치마크 스트링 공식 n!∼ 2 π n ( n e ) n n!\sim\frac{\sqrt{2\pi n}}{(\frac{n}{e})^n} n!~(en)n2πn 즉 n!<2 2 i n!<2^{2^i} n!<22i, 양변 구대수 l o g 2 log2 log2는 1 2 l o g 2(2πn) ⋅ n l o g 2(ne) < 2 i, i≤24\rac{1} {2}log2(2\pi n)\cdot nlog_2(\rac{n}{e}) <2^i, i\le24 21 log2(2πn) ⋅nlog2(en) <2i, i≤24, 폭력 최대 만족 n
typedef long long ll;
//n! = \sqrt{2\pi n}\frac{n}{e}^n
//log_2{n!} = \frac{1}{2}log_2{2\pi n}nlog_2{\frac{n}{e}}
int a[]={3,5,8,12,20,34,57,98,170,300,536,966,1754,3210,5910,10944,20366,38064,71421,134480,254016};
int main(){
int n;
while(scanf("%d",&n),n){
printf("%d
",a[(n-1960)/10]);
}
return 0;
}
T - 단어 찾기 일반 모함수 해석
int a[maxn];
ll f[maxn], g[maxn];
int main()
{
int t; scanf("%d", &t);
while (t--) {
for (int i = 1; i <= 26; ++i) scanf("%d", &a[i]);
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for (int i = 0; i <= a[1]; ++i) {
f[i] = 1;
}
for (int i = 2; i <= 26; ++i) {
for (int j = 0; j <= 50; ++j) {
for (int k = 0; k <= a[i] && i * k + j <= 50; ++k) {
g[i * k + j] += f[j];
}
}
for (int j = 0; j <= 50; ++j) {
f[j] = g[j]; g[j] = 0;
}
}
ll ans = 0;
for (int i = 1; i <= 50; ++i) ans += f[i];
printf("%lld
", ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제이티의 사용에 대한 상세한 설명Continuation 메커니즘을 이용하여 대량의 사용자 요청과 비교적 긴 연결을 처리한다.또한 Jetty는 매우 좋은 인터페이스를 설계했기 때문에 Jetty의 어떤 실현이 사용자의 수요를 만족시키지 못할 때 사용자...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
