QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330341#7609. ColonizationnamelessguguguWA 0ms1692kbC++172.7kb2024-02-17 14:39:132024-02-17 14:39:13

Judging History

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

  • [2024-02-17 14:39:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1692kb
  • [2024-02-17 14:39:13]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <array>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
using std::pair, std::vector, std::array;
const int N = 505, M = 12;
int n, mod;
int inv[N];
int f[N][M][4], g[N][M], h[N][M];
inline void update(int &x, ll y)
{
    x = (x + y) % mod;
}
int ans[M];
int main(void)
{
    scanf("%d%d", &n, &mod);
    inv[1] = 1;
    for (int i = 2; i <= n;++i)
        inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    f[0][0][3] = 1;
    for (int k = 1; k <= 10;++k)
    {
        for (int i = 0; i <= n;++i)
            for (int c = 0; c <= 3;++c)
                update(f[i][k][0], f[i][k - 1][c]);
        for (int i = 1; i <= n;++i)
        {
            g[i][k] = ((ll)f[i - 1][k][1] + f[i - 1][k - 1][2] + f[i - 1][k - 1][3]) % mod;
            if(2 * i < n)
            {
                for (int j = n; j >= i;--j)
                    for (int l = 1, cur = 1; j - i * l >= 0;++l)
                    {
                        cur = (ll)cur * (g[i][k] + l - 1) % mod * inv[l] % mod;
                        for (int c = 0; c <= 3;++c)
                            update(f[j][k][std::min(c + l, 3)], (ll)cur * f[j - i * l][k][c]);
                    }
            }
        }
    }
    for (int k = 1; k <= 10;++k)
    {
        memset(h, 0, sizeof(h));
        for (int i = 1; i <= n;++i)
        {
            update(h[i][k - 1], f[i - 1][k][2]);
            for (int j = 0; j < k;++j)
                for (int l = 1; l < i && l * 2 < n;++l)
                {
                    update(h[i][j], (ll)f[i - l][j][1] * h[l][j + 1]);
                    update(h[i][j], (ll)f[i - l][j][0] * h[l][j]);
                }
        }
        for (int i = 1; i <= k; ++i)
            update(ans[k], g[n][i]);
        for (int i = 0; i < k;++i)
            update(ans[k], h[n][i]);
        if(!(n & 1))
        {
            int sum = 0;
            for (int i = 1; i <= k;++i)
                update(sum, g[n / 2][i]);
            update(ans[k], (ll)sum * (sum + 1) / 2);
            sum = 0;
            for (int i = 1; i < k;++i)
            {
                update(sum, g[n / 2][i]);
                update(ans[k], (ll)sum * h[n / 2][i]);
            }
        }
    }
    for (int k = 10; k >= 1;--k)
        update(ans[k], mod - ans[k - 1]);
    for (int i = 1; i <= std::min(n, 10); ++i)
        printf("%d ", ans[i]);
    for (int i = std::min(n, 10) + 1; i <= n;++i)
        printf("0 ");
    putchar('\n');
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1624kb

input:

3 100000007

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #2:

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

input:

6 300000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #3:

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

input:

10 1000000007

output:

1 104 1 0 0 0 0 0 0 0 

result:

ok 10 numbers

Test #4:

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

input:

2 739878731

output:

1 0 

result:

ok 2 number(s): "1 0"

Test #5:

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

input:

3 122646779

output:

1 0 0 

result:

ok 3 number(s): "1 0 0"

Test #6:

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

input:

4 457287433

output:

1 1 0 0 

result:

ok 4 number(s): "1 1 0 0"

Test #7:

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

input:

5 1000000007

output:

1 2 0 0 0 

result:

ok 5 number(s): "1 2 0 0 0"

Test #8:

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

input:

6 1000000007

output:

1 5 0 0 0 0 

result:

ok 6 numbers

Test #9:

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

input:

7 763596907

output:

1 10 0 0 0 0 0 

result:

ok 7 numbers

Test #10:

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

input:

8 1000000007

output:

1 22 0 0 0 0 0 0 

result:

ok 8 numbers

Test #11:

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

input:

9 729507523

output:

1 46 0 0 0 0 0 0 0 

result:

ok 9 numbers

Test #12:

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

input:

11 488473873

output:

1 230 4 0 0 0 0 0 0 0 0 

result:

ok 11 numbers

Test #13:

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

input:

12 100000007

output:

1 531 19 0 0 0 0 0 0 0 0 0 

result:

ok 12 numbers

Test #14:

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

input:

13 1000000007

output:

1 1223 77 0 0 0 0 0 0 0 0 0 0 

result:

ok 13 numbers

Test #15:

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

input:

14 1000000007

output:

1 2871 287 0 0 0 0 0 0 0 0 0 0 0 

result:

ok 14 numbers

Test #16:

score: -100
Wrong Answer
time: 0ms
memory: 1628kb

input:

15 290707159

output:

1 6737 1003 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 2nd numbers differ - expected: '6738', found: '6737'