QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#542832#8942. Sugar Sweet 3ucup-team1231#AC ✓648ms10828kbC++143.2kb2024-09-01 06:17:502024-09-01 06:17:51

Judging History

你现在查看的是最新测评结果

  • [2024-09-01 06:17:51]
  • 评测
  • 测评结果:AC
  • 用时:648ms
  • 内存:10828kb
  • [2024-09-01 06:17:50]
  • 提交

answer

#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <string>
#include <map>
using namespace std;
const int MOD = 1e9 + 7;

int power(int x, int t) {
    int ret = 1;
    while(t > 0) {
        if(t & 1) ret = 1LL * ret * x % MOD;
        x = 1LL * x * x % MOD;
        t >>= 1;
    }
    return ret;
}
int n, comb[1005][1005];
int px[505][505], pv[505][505], cat[505], tmp[505], ifac[505], fac[505], inv[505];

void init() {
    comb[0][0] = 1;
    for(int i = 1; i <= 2 * n; i++) {
        comb[i][0] = 1;
        for(int j = 1; j <= i; j++) comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }

    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = power(fac[n], MOD - 2);
    for(int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
    for(int i = 1; i <= n; i++) inv[i] = 1LL * ifac[i] * fac[i - 1] % MOD;
    
    for(int i = 1; i <= n; i++) cat[i] = 1LL * inv[i] * comb[2 * i - 2][i - 1] % MOD;

    tmp[0] = 1;
    px[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = n; j >= i; j--) {
            tmp[j] = 0;
            for(int k = i - 1; k < j; k++) tmp[j] = (tmp[j] + 1LL * tmp[k] * cat[j - k]) % MOD;
            px[j][i] = 1LL * tmp[j] * ifac[i] % MOD;
        }
    }

    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) {
        pv[i][j] = 0;
        for(int k = i; k >= 0; k--) pv[i][j] = (1LL * pv[i][j] * j + px[i][k]) % MOD;
    }
}

int a, b, c, x, y, z, t, pc[505][505], av[505], ax[505];

void pmul(int n1, int n2, int n3, int coef) {
    for(int i = 0; i <= n; i++) av[i] = (av[i] + 1LL * pv[n1][i] * pv[n2][i] % MOD * pv[n3][i] % MOD * coef) % MOD;
}

vector<int> interpolate(vector<int> x, vector<int> y, int n) {
    vector<int> res(n), temp(n);
    for(int k = 0; k < n - 1; k++) for(int i = k + 1; i < n; i++)
        y[i] = 1LL * (y[i] - y[k] + MOD) * power((x[i] - x[k] + MOD) % MOD, MOD - 2) % MOD;
    int last = 0; temp[0] = 1;
    for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) {
        res[i] = (res[i] + 1LL * y[k] * temp[i]) % MOD;
        swap(last, temp[i]);
        temp[i] = (temp[i] + 1LL * (MOD - last) * x[k]) % MOD;
    }
    return res;
}

void calc() {
    vector<int> x, y, z;
    for(int i = 0; i <= n; i++) {
        x.push_back(i); y.push_back(av[i]);
    }
    z = interpolate(x, y, n + 1);
    for(int i = 0; i <= n; i++) ax[i] = z[i];
}

int main() {;
    scanf("%d%d%d%d", &a, &b, &c, &t);
    n = a + b + c;
    if(n & 1) {
        printf("0\n"); return 0;
    }
    n /= 2;
    a = n - a; b = n - b; c = n - c;
    if(a < 0 || b < 0 || c < 0) {
        printf("0\n"); return 0;
    }

    init();
    for(int i = 0; i <= a; i++) for(int j = 0; j <= b; j++) for(int k = 0; k <= c; k++) {
        int ci = i + b - j, cj = j + c - k, ck = k + a - i;
        pc[ci][cj] = (pc[ci][cj] + 1LL * comb[ci][i] * comb[cj][j] % MOD * comb[ck][k]) % MOD;
    }
    for(int i = 0; i <= n; i++) for(int j = 0; i + j <= n; j++) {
        int k = n - i - j;
        pmul(i, j, k, pc[i][j]);
    }
    calc();

    int ans = 0;
    for(int i = 0; i <= n; i++) ans = (ans + 1LL * ax[i] * fac[i] % MOD * power(i, t)) % MOD;
    printf("%d\n", ans);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6188kb

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8220kb

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 5784kb

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 325ms
memory: 10232kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

score: 0
Accepted
time: 247ms
memory: 10468kb

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

score: 0
Accepted
time: 1ms
memory: 5888kb

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

score: 0
Accepted
time: 1ms
memory: 7916kb

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 1ms
memory: 5868kb

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 330ms
memory: 9756kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 332ms
memory: 8980kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

score: 0
Accepted
time: 5ms
memory: 7888kb

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 637ms
memory: 10708kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 648ms
memory: 10752kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 633ms
memory: 10776kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 637ms
memory: 9728kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 639ms
memory: 10728kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 646ms
memory: 10828kb

input:

300 300 400 75787941

output:

778545661

result:

ok 1 number(s): "778545661"

Test #20:

score: 0
Accepted
time: 1ms
memory: 7924kb

input:

7 16 11 1568

output:

725510153

result:

ok 1 number(s): "725510153"

Extra Test:

score: 0
Extra Test Passed