Тема: Задача Кактусы
Как можно решить такую задачу ?
http://algoprog.kz/ej/contests/5/statements/kaktusi/
Заранее спасибо!!!
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Задача Кактусы
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Как можно решить такую задачу ?
http://algoprog.kz/ej/contests/5/statements/kaktusi/
Заранее спасибо!!!
Как решать не знаю, но здесь http://neerc.ifmo.ru/school/io/archive/ … ced-02.rar лежит архив с тестами и решениями, может поможет разобраться
Код непонятый. Объясните плз, в чем идеа!!!! вот Код:
import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class cacti_as implements Runnable {
final long MOD = 1000000007;
final long INV2 = BigInteger.valueOf(2).modInverse(BigInteger.valueOf(MOD)).longValue();
public void solve() throws IOException {
Scanner in = new Scanner(new File("cacti.in"));
PrintWriter out = new PrintWriter("cacti.out");
int n = in.nextInt();
long[] fact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = (fact[i - 1]) * i % MOD;
}
long[][] c = new long[n + 1][n + 1];
c[0][0] = 1;
for (int i = 1; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= n; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
long[] a = new long[n + 1];
long[] ah = new long[n + 1];
a[0] = ah[0] = 1;
a[1] = ah[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k <= i - 1; k++) {
ah[i] = (ah[i] + (k * c[i - 2][k - 1] % MOD * a[k] % MOD * ah[i - k]) % MOD) % MOD;
}
for (int l = 3; l <= i; l++) {
long[][] d = new long[l][i - l + 1];
for (int k = 0; k <= i - l; k++) {
d[0][k] = (c[i - 1][k] * ah[k + 1]) % MOD;
}
for (int j = 1; j < l; j++) {
for (int k = 0; k <= i - l; k++) {
for (int t = 0; t <= k; t++) {
d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * ah[t + 1] % MOD * (t + 1) % MOD) % MOD;
}
}
}
a[i] = (a[i] + d[l - 1][i - l] * INV2) % MOD;
}
a[i] = (a[i] + ah[i]) % MOD;
// System.out.println(a[i]);
}
out.println(a[n]);
long[] b = new long[n + 1];
long[] bh = new long[n + 1];
b[0] = bh[0] = 1;
b[1] = bh[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k <= i - 1; k++) {
bh[i] = (bh[i] + (k * c[i - 2][k - 1] % MOD * b[k] % MOD * b[i - k]) % MOD) % MOD;
}
for (int l = 3; l <= i; l++) {
long[][] d = new long[l][i - l + 1];
for (int k = 0; k <= i - l; k++) {
d[0][k] = (c[i - 2][k] * b[k + 1]) % MOD;
}
for (int j = 1; j < l; j++) {
for (int k = 0; k <= i - l; k++) {
for (int t = 0; t <= k; t++) {
d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * b[t + 1] % MOD * (t + 1) % MOD) % MOD;
}
}
}
b[i] = (b[i] + d[l - 1][i - l] * INV2) % MOD;
}
b[i] = (b[i] + bh[i]) % MOD;
System.out.println(b[i]);
}
out.println(b[n]);
in.close();
out.close();
}
public void run() {
try {
solve();
} catch (IOException e) {
}
}
public static void main(String[] arg) {
new Thread(new cacti_as()).start();
}
}
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Задача Кактусы