QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#542832 | #8942. Sugar Sweet 3 | ucup-team1231# | AC ✓ | 648ms | 10828kb | C++14 | 3.2kb | 2024-09-01 06:17:50 | 2024-09-01 06:17:51 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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