QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449778#8717. 骰子Andyqian7WA 1ms7672kbC++142.0kb2024-06-21 17:05:242024-06-21 17:05:24

Judging History

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

  • [2024-06-21 17:05:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7672kb
  • [2024-06-21 17:05:24]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;
int n, m, q, b[300], p[2000][300], zero[300], pre[300][300], ipre[300][300], pre2[300][300];
int fp(int x, int k)
{
    if (!k)
        return 1;
    if (k & 1)
        return fp(x, k - 1) * x % mod;
    int tmp = fp(x, k >> 1);
    return tmp * tmp % mod;
}
int inv(int x)
{
    return fp(x, mod - 2);
}
void mul(int *a, int *b, int *c)
{
    for (int i = 0; i <= m; i++)
    {
        c[i] = 0;
        for (int j = 0; j <= m; j++)
        {
            c[i] += b[i] * a[i - j];
            c[i] %= mod;
        }
    }
}
void inv(int *a, int *b)
{
    b[0] = inv(a[0]);
    for (int i = 1; i <= m; i++)
    {
        b[i] = 0;
        for (int j = 0; j < i; j++)
        {
            b[i] += a[i - j] * b[j];
            b[i] %= mod;
        }
        b[i] = (mod - b[i]) * b[0] % mod;
    }
}
signed main()
{
    cin >> n >> m >> q;
    for (int i = 0; i <= m; i++)
    {
        cin >> b[m - i];
    }
    for (int i = 1; i <= n; i++)
    {
        bool sign = false;
        for (int j = 0; j <= m; j++)
        {
            int tmp;
            cin >> tmp;
            tmp %= mod;
            if (tmp)
                sign = true;
            if (sign)
            {
                p[i][j - zero[i]] = tmp;
            }
            else
            {
                zero[i]++;
            }
        }
        zero[i] += zero[i - 1];
    }
    ipre[0][0] = pre[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        mul(pre[i - 1], p[i], pre[i]);
        inv(pre[i], ipre[i]);
        mul(pre[i], b, pre2[i]);
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for (int i = 0; i <= m - zero[r] + zero[l - 1]; i++)
        {
            ans += pre2[r][i] * ipre[l - 1][m - zero[r] + zero[l - 1] - i];
            ans %= mod;
        }
        cout << ans << endl;
    }
}

详细

Test #1:

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

input:

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

output:

3
1
0

result:

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

Test #2:

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

input:

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

output:

2
1
0
3
1
2

result:

ok 6 numbers

Test #3:

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

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

604063100

result:

wrong answer 1st numbers differ - expected: '148903503', found: '604063100'