ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213566 | #2769. 覆盖 | STASISZHY | 0 | 0ms | 0kb | C++11 | 1.7kb | 2024-11-12 20:53:45 | 2024-11-12 23:38:59 |
answer
// Problem: D. 子序列
// Contest: undefined - NOIP2024训练赛 03
// URL: http://119.28.3.174/contest/1155/problem/2770
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#pragma GCC optmize("OFAST");
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10, M = 1e6 + 10, mod = 998244353, INF = 0x3f3f3f3f;
int n, m, q, ans;
int s[N], dp[N];
vector<int> e[N];
struct Tree
{
int l, r, sum[30] = {};
}tr[N << 2];
Tree merge(Tree a, Tree b)
{
Tree res; res.l = a.l, res.r = b.r;
for(int i = 0; i < m; i ++)
{
for(int x = 0; x < m; x ++)
{
int y = i - x; if(y < 0) y += m;
res.sum[i % m] = (res.sum[i % m] + a.sum[x] * b.sum[y]) % mod;
}
}
return res;
}
inline void pushup(int x) {tr[x] = merge(tr[2 * x], tr[2 * x + 1]);}
void build(int x, int l, int r)
{
tr[x].l = l, tr[x].r = r;
if(l == r)
{
tr[x].sum[s[l] % m] = 1, tr[x].sum[0] += 1;
return;
}
int mid = l + r >> 1;
build(2 * x, l, mid);
build(2 * x + 1, mid + 1, r);
pushup(x);
}
Tree query(int x, int l, int r)
{
if(tr[x].l >= l && tr[x].r <= r) return tr[x];
int mid = tr[x].l + tr[x].r >> 1;
if(l > mid) return query(2 * x + 1, l, r);
else if(r <= mid) return query(2 * x, l, r);
else return merge(query(2 * x, l, r), query(2 * x + 1, l, r));
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> s[i];
build(1, 1, n);
cin >> q;
while(q --)
{
int l, r; cin >> l >> r;
cout << query(1, l, r).sum[0] << '\n';
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
20 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 13 17 15 18 16 19 17 20 18 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
input:
1000 2 1 3 2 4 3 5 4 6 3 7 6 8 7 9 8 10 9 11 10 12 5 13 11 14 13 15 14 16 15 17 12 18 16 19 18 20 19...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
2000000 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 11 15 14 16 13 17 15 18 16 19 17 2...