首页 > 其他分享 >YACS 2023年5月月赛 甲组 T1 子集和（六） 题解

YACS 2023年5月月赛 甲组 T1 子集和（六） 题解

时间：2023-05-17 20:26:01浏览次数：55  
标签：YACS GCC int 题解 mid 甲组 ++ pragma optimize

YACS 老师说这是道分治，但就不告诉我怎么做，我硬是用线段树卡了过去...特别解气的是把 AC 图片发了过去（我就是在 YACS 上的编程课）

莫队

好了说点正经的，看到是谁谁谁的倍数就能想到 DP，状态设计也很水啦！设 f[i] 为当前考虑到的区间内，子集和 % k = i 的数量。

新加入一个元素时，循环 0 ~ k - 1，更新 f[i] = f[i - value] + f[i]（value 是当前加的值，i - value 有可能为负，要取个模大家自己去弄）

这里还不能滚动数组，因为最前面的还会用到最后面的。

每次询问把 $f$ 清空，然后对参数 $l$ $r$ 做 DP 就可以做到 $O(qnk)$ 的复杂度，显然爆炸。

接着就开始了漫长的优化之旅。

首先让我想到的，是莫队，但是这个 dp 它不支持删除元素啊，所以还要搞不删除莫队，我懒了直接用在线莫队。

在线莫队我讲过，这里不废话，时间复杂度就是 $O(q\sqrt{n}\cdot k)$，然后循环展开了只能过 7 个点，看来是取模的问题。

#include <cmath>
#include <iostream>
using namespace std;
//此题时间比较紧，所以要使用 fread 快读（读入正数）
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : * p1 ++)
inline int read () {
    int x = 0;
    char ch = getchar ();
    while (!isdigit(ch) ) ch = getchar ();
    while (isdigit(ch) ) {
        x = x * 10 + (ch ^ 48);
        ch = getchar ();
    }
    return x;
}
const int mod = 998244353, b = 317;
int n, q, k;
int x, y, l, r;
int a[100005], t[20], ans[20];
int pre[318][318][20];//块长 317
//pre[i][j]:以第 i 个块第一个为首，第 j 个块最后一个为尾
inline void add (int x) {
    int i;
    for (i = 0; i + 5 < k; i += 5) {
        t[i] = (ans[i] + ans[(i - x + k) % k]) % 998244353;
        t[i + 1] = (ans[i + 1] + ans[(i + 1 - x + k) % k]) % 998244353;
        t[i + 2] = (ans[i + 2] + ans[(i + 2 - x + k) % k]) % 998244353;
        t[i + 3] = (ans[i + 3] + ans[(i + 3 - x + k) % k]) % 998244353;
        t[i + 4] = (ans[i + 4] + ans[(i + 4 - x + k) % k]) % 998244353;
    }
    while (i < k) {
        t[i] = (ans[i] + ans[(i - x + k) % k]) % 998244353;
        ++ i;
    }
    for (i = 0; i + 5 < k; i += 5) {
        ans[i] = t[i];
        ans[i + 1] = t[i + 1];
        ans[i + 2] = t[i + 2];
        ans[i + 3] = t[i + 3];
        ans[i + 4] = t[i + 4];
    }
    while (i < k) {
        ans[i] = t[i];
        ++ i;
    }
}
inline int sec (int x) {return (x - 1) / b + 1;}
int main () {
    n = read (); q = read (); k = read ();
    for (register int i = 1; i <= n; i ++) {
        a[i] = read ();
        a[i] %= k;
    }
    //在线不删除莫队的预处理
    for (register int i = 1; i * b <= n; i ++) {
        for (register int j = i; j * b <= n; j ++) {
            //复刻
            for (register int l = 0; l < k; l ++) pre[i][j][l] = pre[i][j - 1][l];
            if (i == j) pre[i][j][0] = 1;
            x = i; y = j;
            for (register int l = (j - 1) * b + 1; sec (l) == j; l ++) {
                for (register int i = 0; i < k; i ++) t[i] = pre[x][y][i] + pre[x][y][(i - a[l] + k) % k];
                for (register int i = 0; i < k; i ++) pre[x][y][i] = t[i] % mod;
            }
        }
    }
    //输入询问
    while (q --) { 
        x = read (); y = read ();
        int b_x = ceil ( (x - 1) * 1.0 / b) + 1, b_y = (y - 1) / b;//第一个大于 x 的块编号和第一个小于 y 的块编号
        for (register int i = 0; i < k; i ++) ans[i] = pre[b_x][b_y][i];
        if (b_x > b_y) {//直接暴力
            ans[0] = 1;
            for (int i = x; i <= y; i ++) add (a[i]);
            printf ("%d\n", ans[0]);
            continue;
        }
        l = (b_x - 1) * b + 1;
        r = b_y * b;
        while (l > x) add (a[-- l]);
        while (r < y) add (a[++ r]);
        printf ("%d\n", ans[0]);
    }
    return 0;
}

线段树

上完编程课回家的路上，我就一直在想怎么分治，意间想到 cdq，但是怎么合并区间呢？我于是想到了 $O(k^2)$ 的合并两个 $f$ 数组，

然后再一想，那不就可以用线段树维护了？假如现在有两个 dp 数组叫 $g$ 和 $f$，那么合并的代码如下：

void merge (){
        for (int i = 0; i < k; i ++) {
                for (int j = 0; j < k; j ++) {
                        ans[(i + j) % k] += f[i] * g[j];
                }
        }
}

解释一下，假如现在 $f$ 数组中拼成 $i$ 的情况有 $f[i]$ 种，$g$ 数组中拼成 $j$ 的情况有 $g[j]$ 种。

那么拼成 $i+j$ 的情况我们从 $f[i]$ 和 $g[j]$ 中各选一个就行了，方案数就是两者相乘。

$query$ 的写法几乎不变，如果你不会，请移步洛谷：小白逛公园。

于是就有了 $q\cdot n\cdot log_n\cdot k^2$ 的代码，显然过不掉，60 分，正常的代码：

#include <iostream>
#define int long long
using namespace std;
int n, q, k;
int x, y, c[100005];
const int mod = 998244353;
struct Tree {long long f[20];}a[400005];
Tree merge (Tree x, Tree y) {
    Tree ret;
    for (int i = 0; i < k; i ++) ret.f[i] = 0;
    for (int i = 0; i < k; i ++) {
        for (int j = 0; j < k; j ++) {
            int l = i + j;
            if (l >= k) l -= k;
            ret.f[l] = (ret.f[l] + x.f[i] * y.f[j] % mod) % mod;
        }
    }
    return ret;
}
void build (int l, int r, int k) {
    if (l == r) {
        for (int i = 0; i < k; i ++) a[k].f[i] = 0;
        ++ a[k].f[0]; ++ a[k].f[c[l] ];
        return;
    }
    int mid = l + r >> 1;
    build (l, mid, k << 1);
    build (mid + 1, r, k << 1 | 1);
    a[k] = merge (a[k << 1], a[k << 1 | 1]);
}
Tree query (int l, int r, int k) {
    if (x <= l && y >= r) return a[k];
    int mid = l + r >> 1;
    Tree ret;
    ret.f[0] = 1;
    if (x <= mid) ret = query (l, mid, k << 1);
    if (y > mid) ret = merge (ret, query (mid + 1, r, k << 1 | 1) );
    return ret;
}
signed main () {
    scanf ("%lld%lld%lld", &n, &q, &k);
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld", &c[i]);
        c[i] %= k;
    }
    build (1, n, 1);
    while (q --) {
        scanf ("%lld%lld", &x, &y);
        printf ("%lld\n", query (1, n, 1).f[0]);
    }
    return 0;
}

然后我想可不可以优化合并呢？一看，这不是卷积吗？（雾

可以写个 FFT，优化成 $O(q\cdot n\cdot k\log k)$，然后大概能过，不仅可以装逼，还可以让老师打脸。

但是，我不会 FFT 啊，怎么办啊！取模耗费了大量时间，因此把取模换成减就能块好几倍，然而还是过不掉最后四个点。

这时候就要使出绝招——打表了！老师告诉我正解复杂度为 $O(q\log n\cdot k)$，所以终测的 $k$ 一定都是 $19$ $20$ 的。

我就写了个程序特判 $19$ $20$ 的，具体说就是把 $ans$ 数组每一项用 $f$ $g$ 表示出来，不要写两层循环。

取模很多，所以 TLE，但仔细一想，可以把多个加到一起再取模啊，于是 $10$ 个 $10$ 个加到一起又开了 $ull$ 就好了。

时间复杂度最优为 $O(q\log n)$，甚至比正解还少掉一个 $k$（

代码超级不正常，谨慎食用：

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 15, stdin), p1 == p2) ? EOF : * p1 ++)
inline int read() {
    int x = 0;
    char ch = getchar ();
    while (!isdigit(ch) ) ch = getchar ();
    while (isdigit(ch) ) {
        x = x * 10 + ch - 48;
        ch = getchar ();
    }
    return x;
}
int n, q, k;
int x, y, c[100005];
const int mod = 998244353;
struct Tree {unsigned long long f[20];}a[400005], t;
Tree stack[1005];
int top;
void merge (Tree x, Tree y) {
    for (int i = 0; i < k; i ++) t.f[i] = 0;
    if (k == 20) {
        t.f[0]=((x.f[0]*y.f[0]+x.f[1]*y.f[19]+x.f[2]*y.f[18]+x.f[3]*y.f[17]+x.f[4]*y.f[16]+x.f[5]*y.f[15]+x.f[6]*y.f[14]+x.f[7]*y.f[13]+x.f[8]*y.f[12]+x.f[9]*y.f[11])%mod+(x.f[10]*y.f[10]+x.f[11]*y.f[9]+x.f[12]*y.f[8]+x.f[13]*y.f[7]+x.f[14]*y.f[6]+x.f[15]*y.f[5]+x.f[16]*y.f[4]+x.f[17]*y.f[3]+x.f[18]*y.f[2]+x.f[19]*y.f[1])%mod)%mod;
        t.f[1]=((x.f[0]*y.f[1]+x.f[1]*y.f[0]+x.f[2]*y.f[19]+x.f[3]*y.f[18]+x.f[4]*y.f[17]+x.f[5]*y.f[16]+x.f[6]*y.f[15]+x.f[7]*y.f[14]+x.f[8]*y.f[13]+x.f[9]*y.f[12])%mod+(x.f[10]*y.f[11]+x.f[11]*y.f[10]+x.f[12]*y.f[9]+x.f[13]*y.f[8]+x.f[14]*y.f[7]+x.f[15]*y.f[6]+x.f[16]*y.f[5]+x.f[17]*y.f[4]+x.f[18]*y.f[3]+x.f[19]*y.f[2])%mod)%mod;
        t.f[2]=((x.f[0]*y.f[2]+x.f[1]*y.f[1]+x.f[2]*y.f[0]+x.f[3]*y.f[19]+x.f[4]*y.f[18]+x.f[5]*y.f[17]+x.f[6]*y.f[16]+x.f[7]*y.f[15]+x.f[8]*y.f[14]+x.f[9]*y.f[13])%mod+(x.f[10]*y.f[12]+x.f[11]*y.f[11]+x.f[12]*y.f[10]+x.f[13]*y.f[9]+x.f[14]*y.f[8]+x.f[15]*y.f[7]+x.f[16]*y.f[6]+x.f[17]*y.f[5]+x.f[18]*y.f[4]+x.f[19]*y.f[3])%mod)%mod;
        t.f[3]=((x.f[0]*y.f[3]+x.f[1]*y.f[2]+x.f[2]*y.f[1]+x.f[3]*y.f[0]+x.f[4]*y.f[19]+x.f[5]*y.f[18]+x.f[6]*y.f[17]+x.f[7]*y.f[16]+x.f[8]*y.f[15]+x.f[9]*y.f[14])%mod+(x.f[10]*y.f[13]+x.f[11]*y.f[12]+x.f[12]*y.f[11]+x.f[13]*y.f[10]+x.f[14]*y.f[9]+x.f[15]*y.f[8]+x.f[16]*y.f[7]+x.f[17]*y.f[6]+x.f[18]*y.f[5]+x.f[19]*y.f[4])%mod)%mod;
        t.f[4]=((x.f[0]*y.f[4]+x.f[1]*y.f[3]+x.f[2]*y.f[2]+x.f[3]*y.f[1]+x.f[4]*y.f[0]+x.f[5]*y.f[19]+x.f[6]*y.f[18]+x.f[7]*y.f[17]+x.f[8]*y.f[16]+x.f[9]*y.f[15])%mod+(x.f[10]*y.f[14]+x.f[11]*y.f[13]+x.f[12]*y.f[12]+x.f[13]*y.f[11]+x.f[14]*y.f[10]+x.f[15]*y.f[9]+x.f[16]*y.f[8]+x.f[17]*y.f[7]+x.f[18]*y.f[6]+x.f[19]*y.f[5])%mod)%mod;
        t.f[5]=((x.f[0]*y.f[5]+x.f[1]*y.f[4]+x.f[2]*y.f[3]+x.f[3]*y.f[2]+x.f[4]*y.f[1]+x.f[5]*y.f[0]+x.f[6]*y.f[19]+x.f[7]*y.f[18]+x.f[8]*y.f[17]+x.f[9]*y.f[16])%mod+(x.f[10]*y.f[15]+x.f[11]*y.f[14]+x.f[12]*y.f[13]+x.f[13]*y.f[12]+x.f[14]*y.f[11]+x.f[15]*y.f[10]+x.f[16]*y.f[9]+x.f[17]*y.f[8]+x.f[18]*y.f[7]+x.f[19]*y.f[6])%mod)%mod;
        t.f[6]=((x.f[0]*y.f[6]+x.f[1]*y.f[5]+x.f[2]*y.f[4]+x.f[3]*y.f[3]+x.f[4]*y.f[2]+x.f[5]*y.f[1]+x.f[6]*y.f[0]+x.f[7]*y.f[19]+x.f[8]*y.f[18]+x.f[9]*y.f[17])%mod+(x.f[10]*y.f[16]+x.f[11]*y.f[15]+x.f[12]*y.f[14]+x.f[13]*y.f[13]+x.f[14]*y.f[12]+x.f[15]*y.f[11]+x.f[16]*y.f[10]+x.f[17]*y.f[9]+x.f[18]*y.f[8]+x.f[19]*y.f[7])%mod)%mod;
        t.f[7]=((x.f[0]*y.f[7]+x.f[1]*y.f[6]+x.f[2]*y.f[5]+x.f[3]*y.f[4]+x.f[4]*y.f[3]+x.f[5]*y.f[2]+x.f[6]*y.f[1]+x.f[7]*y.f[0]+x.f[8]*y.f[19]+x.f[9]*y.f[18])%mod+(x.f[10]*y.f[17]+x.f[11]*y.f[16]+x.f[12]*y.f[15]+x.f[13]*y.f[14]+x.f[14]*y.f[13]+x.f[15]*y.f[12]+x.f[16]*y.f[11]+x.f[17]*y.f[10]+x.f[18]*y.f[9]+x.f[19]*y.f[8])%mod)%mod;
        t.f[8]=((x.f[0]*y.f[8]+x.f[1]*y.f[7]+x.f[2]*y.f[6]+x.f[3]*y.f[5]+x.f[4]*y.f[4]+x.f[5]*y.f[3]+x.f[6]*y.f[2]+x.f[7]*y.f[1]+x.f[8]*y.f[0]+x.f[9]*y.f[19])%mod+(x.f[10]*y.f[18]+x.f[11]*y.f[17]+x.f[12]*y.f[16]+x.f[13]*y.f[15]+x.f[14]*y.f[14]+x.f[15]*y.f[13]+x.f[16]*y.f[12]+x.f[17]*y.f[11]+x.f[18]*y.f[10]+x.f[19]*y.f[9])%mod)%mod;
        t.f[9]=((x.f[0]*y.f[9]+x.f[1]*y.f[8]+x.f[2]*y.f[7]+x.f[3]*y.f[6]+x.f[4]*y.f[5]+x.f[5]*y.f[4]+x.f[6]*y.f[3]+x.f[7]*y.f[2]+x.f[8]*y.f[1]+x.f[9]*y.f[0])%mod+(x.f[10]*y.f[19]+x.f[11]*y.f[18]+x.f[12]*y.f[17]+x.f[13]*y.f[16]+x.f[14]*y.f[15]+x.f[15]*y.f[14]+x.f[16]*y.f[13]+x.f[17]*y.f[12]+x.f[18]*y.f[11]+x.f[19]*y.f[10])%mod)%mod;
        t.f[10]=((x.f[0]*y.f[10]+x.f[1]*y.f[9]+x.f[2]*y.f[8]+x.f[3]*y.f[7]+x.f[4]*y.f[6]+x.f[5]*y.f[5]+x.f[6]*y.f[4]+x.f[7]*y.f[3]+x.f[8]*y.f[2]+x.f[9]*y.f[1])%mod+(x.f[10]*y.f[0]+x.f[11]*y.f[19]+x.f[12]*y.f[18]+x.f[13]*y.f[17]+x.f[14]*y.f[16]+x.f[15]*y.f[15]+x.f[16]*y.f[14]+x.f[17]*y.f[13]+x.f[18]*y.f[12]+x.f[19]*y.f[11])%mod)%mod;
        t.f[11]=((x.f[0]*y.f[11]+x.f[1]*y.f[10]+x.f[2]*y.f[9]+x.f[3]*y.f[8]+x.f[4]*y.f[7]+x.f[5]*y.f[6]+x.f[6]*y.f[5]+x.f[7]*y.f[4]+x.f[8]*y.f[3]+x.f[9]*y.f[2])%mod+(x.f[10]*y.f[1]+x.f[11]*y.f[0]+x.f[12]*y.f[19]+x.f[13]*y.f[18]+x.f[14]*y.f[17]+x.f[15]*y.f[16]+x.f[16]*y.f[15]+x.f[17]*y.f[14]+x.f[18]*y.f[13]+x.f[19]*y.f[12])%mod)%mod;
        t.f[12]=((x.f[0]*y.f[12]+x.f[1]*y.f[11]+x.f[2]*y.f[10]+x.f[3]*y.f[9]+x.f[4]*y.f[8]+x.f[5]*y.f[7]+x.f[6]*y.f[6]+x.f[7]*y.f[5]+x.f[8]*y.f[4]+x.f[9]*y.f[3])%mod+(x.f[10]*y.f[2]+x.f[11]*y.f[1]+x.f[12]*y.f[0]+x.f[13]*y.f[19]+x.f[14]*y.f[18]+x.f[15]*y.f[17]+x.f[16]*y.f[16]+x.f[17]*y.f[15]+x.f[18]*y.f[14]+x.f[19]*y.f[13])%mod)%mod;
        t.f[13]=((x.f[0]*y.f[13]+x.f[1]*y.f[12]+x.f[2]*y.f[11]+x.f[3]*y.f[10]+x.f[4]*y.f[9]+x.f[5]*y.f[8]+x.f[6]*y.f[7]+x.f[7]*y.f[6]+x.f[8]*y.f[5]+x.f[9]*y.f[4])%mod+(x.f[10]*y.f[3]+x.f[11]*y.f[2]+x.f[12]*y.f[1]+x.f[13]*y.f[0]+x.f[14]*y.f[19]+x.f[15]*y.f[18]+x.f[16]*y.f[17]+x.f[17]*y.f[16]+x.f[18]*y.f[15]+x.f[19]*y.f[14])%mod)%mod;
        t.f[14]=((x.f[0]*y.f[14]+x.f[1]*y.f[13]+x.f[2]*y.f[12]+x.f[3]*y.f[11]+x.f[4]*y.f[10]+x.f[5]*y.f[9]+x.f[6]*y.f[8]+x.f[7]*y.f[7]+x.f[8]*y.f[6]+x.f[9]*y.f[5])%mod+(x.f[10]*y.f[4]+x.f[11]*y.f[3]+x.f[12]*y.f[2]+x.f[13]*y.f[1]+x.f[14]*y.f[0]+x.f[15]*y.f[19]+x.f[16]*y.f[18]+x.f[17]*y.f[17]+x.f[18]*y.f[16]+x.f[19]*y.f[15])%mod)%mod;
        t.f[15]=((x.f[0]*y.f[15]+x.f[1]*y.f[14]+x.f[2]*y.f[13]+x.f[3]*y.f[12]+x.f[4]*y.f[11]+x.f[5]*y.f[10]+x.f[6]*y.f[9]+x.f[7]*y.f[8]+x.f[8]*y.f[7]+x.f[9]*y.f[6])%mod+(x.f[10]*y.f[5]+x.f[11]*y.f[4]+x.f[12]*y.f[3]+x.f[13]*y.f[2]+x.f[14]*y.f[1]+x.f[15]*y.f[0]+x.f[16]*y.f[19]+x.f[17]*y.f[18]+x.f[18]*y.f[17]+x.f[19]*y.f[16])%mod)%mod;
        t.f[16]=((x.f[0]*y.f[16]+x.f[1]*y.f[15]+x.f[2]*y.f[14]+x.f[3]*y.f[13]+x.f[4]*y.f[12]+x.f[5]*y.f[11]+x.f[6]*y.f[10]+x.f[7]*y.f[9]+x.f[8]*y.f[8]+x.f[9]*y.f[7])%mod+(x.f[10]*y.f[6]+x.f[11]*y.f[5]+x.f[12]*y.f[4]+x.f[13]*y.f[3]+x.f[14]*y.f[2]+x.f[15]*y.f[1]+x.f[16]*y.f[0]+x.f[17]*y.f[19]+x.f[18]*y.f[18]+x.f[19]*y.f[17])%mod)%mod;
        t.f[17]=((x.f[0]*y.f[17]+x.f[1]*y.f[16]+x.f[2]*y.f[15]+x.f[3]*y.f[14]+x.f[4]*y.f[13]+x.f[5]*y.f[12]+x.f[6]*y.f[11]+x.f[7]*y.f[10]+x.f[8]*y.f[9]+x.f[9]*y.f[8])%mod+(x.f[10]*y.f[7]+x.f[11]*y.f[6]+x.f[12]*y.f[5]+x.f[13]*y.f[4]+x.f[14]*y.f[3]+x.f[15]*y.f[2]+x.f[16]*y.f[1]+x.f[17]*y.f[0]+x.f[18]*y.f[19]+x.f[19]*y.f[18])%mod)%mod;
        t.f[18]=((x.f[0]*y.f[18]+x.f[1]*y.f[17]+x.f[2]*y.f[16]+x.f[3]*y.f[15]+x.f[4]*y.f[14]+x.f[5]*y.f[13]+x.f[6]*y.f[12]+x.f[7]*y.f[11]+x.f[8]*y.f[10]+x.f[9]*y.f[9])%mod+(x.f[10]*y.f[8]+x.f[11]*y.f[7]+x.f[12]*y.f[6]+x.f[13]*y.f[5]+x.f[14]*y.f[4]+x.f[15]*y.f[3]+x.f[16]*y.f[2]+x.f[17]*y.f[1]+x.f[18]*y.f[0]+x.f[19]*y.f[19])%mod)%mod;
        t.f[19]=((x.f[0]*y.f[19]+x.f[1]*y.f[18]+x.f[2]*y.f[17]+x.f[3]*y.f[16]+x.f[4]*y.f[15]+x.f[5]*y.f[14]+x.f[6]*y.f[13]+x.f[7]*y.f[12]+x.f[8]*y.f[11]+x.f[9]*y.f[10])%mod+(x.f[10]*y.f[9]+x.f[11]*y.f[8]+x.f[12]*y.f[7]+x.f[13]*y.f[6]+x.f[14]*y.f[5]+x.f[15]*y.f[4]+x.f[16]*y.f[3]+x.f[17]*y.f[2]+x.f[18]*y.f[1]+x.f[19]*y.f[0])%mod)%mod;
    } else if (k == 19) {
        t.f[0]=((x.f[0]*y.f[0]+x.f[1]*y.f[18]+x.f[2]*y.f[17]+x.f[3]*y.f[16]+x.f[4]*y.f[15]+x.f[5]*y.f[14]+x.f[6]*y.f[13]+x.f[7]*y.f[12]+x.f[8]*y.f[11]+x.f[9]*y.f[10])%mod+(x.f[10]*y.f[9]+x.f[11]*y.f[8]+x.f[12]*y.f[7]+x.f[13]*y.f[6]+x.f[14]*y.f[5]+x.f[15]*y.f[4]+x.f[16]*y.f[3]+x.f[17]*y.f[2]+x.f[18]*y.f[1])%mod)%mod;
        t.f[1]=((x.f[0]*y.f[1]+x.f[1]*y.f[0]+x.f[2]*y.f[18]+x.f[3]*y.f[17]+x.f[4]*y.f[16]+x.f[5]*y.f[15]+x.f[6]*y.f[14]+x.f[7]*y.f[13]+x.f[8]*y.f[12]+x.f[9]*y.f[11])%mod+(x.f[10]*y.f[10]+x.f[11]*y.f[9]+x.f[12]*y.f[8]+x.f[13]*y.f[7]+x.f[14]*y.f[6]+x.f[15]*y.f[5]+x.f[16]*y.f[4]+x.f[17]*y.f[3]+x.f[18]*y.f[2])%mod)%mod;
        t.f[2]=((x.f[0]*y.f[2]+x.f[1]*y.f[1]+x.f[2]*y.f[0]+x.f[3]*y.f[18]+x.f[4]*y.f[17]+x.f[5]*y.f[16]+x.f[6]*y.f[15]+x.f[7]*y.f[14]+x.f[8]*y.f[13]+x.f[9]*y.f[12])%mod+(x.f[10]*y.f[11]+x.f[11]*y.f[10]+x.f[12]*y.f[9]+x.f[13]*y.f[8]+x.f[14]*y.f[7]+x.f[15]*y.f[6]+x.f[16]*y.f[5]+x.f[17]*y.f[4]+x.f[18]*y.f[3])%mod)%mod;
        t.f[3]=((x.f[0]*y.f[3]+x.f[1]*y.f[2]+x.f[2]*y.f[1]+x.f[3]*y.f[0]+x.f[4]*y.f[18]+x.f[5]*y.f[17]+x.f[6]*y.f[16]+x.f[7]*y.f[15]+x.f[8]*y.f[14]+x.f[9]*y.f[13])%mod+(x.f[10]*y.f[12]+x.f[11]*y.f[11]+x.f[12]*y.f[10]+x.f[13]*y.f[9]+x.f[14]*y.f[8]+x.f[15]*y.f[7]+x.f[16]*y.f[6]+x.f[17]*y.f[5]+x.f[18]*y.f[4])%mod)%mod;
        t.f[4]=((x.f[0]*y.f[4]+x.f[1]*y.f[3]+x.f[2]*y.f[2]+x.f[3]*y.f[1]+x.f[4]*y.f[0]+x.f[5]*y.f[18]+x.f[6]*y.f[17]+x.f[7]*y.f[16]+x.f[8]*y.f[15]+x.f[9]*y.f[14])%mod+(x.f[10]*y.f[13]+x.f[11]*y.f[12]+x.f[12]*y.f[11]+x.f[13]*y.f[10]+x.f[14]*y.f[9]+x.f[15]*y.f[8]+x.f[16]*y.f[7]+x.f[17]*y.f[6]+x.f[18]*y.f[5])%mod)%mod;
        t.f[5]=((x.f[0]*y.f[5]+x.f[1]*y.f[4]+x.f[2]*y.f[3]+x.f[3]*y.f[2]+x.f[4]*y.f[1]+x.f[5]*y.f[0]+x.f[6]*y.f[18]+x.f[7]*y.f[17]+x.f[8]*y.f[16]+x.f[9]*y.f[15])%mod+(x.f[10]*y.f[14]+x.f[11]*y.f[13]+x.f[12]*y.f[12]+x.f[13]*y.f[11]+x.f[14]*y.f[10]+x.f[15]*y.f[9]+x.f[16]*y.f[8]+x.f[17]*y.f[7]+x.f[18]*y.f[6])%mod)%mod;
        t.f[6]=((x.f[0]*y.f[6]+x.f[1]*y.f[5]+x.f[2]*y.f[4]+x.f[3]*y.f[3]+x.f[4]*y.f[2]+x.f[5]*y.f[1]+x.f[6]*y.f[0]+x.f[7]*y.f[18]+x.f[8]*y.f[17]+x.f[9]*y.f[16])%mod+(x.f[10]*y.f[15]+x.f[11]*y.f[14]+x.f[12]*y.f[13]+x.f[13]*y.f[12]+x.f[14]*y.f[11]+x.f[15]*y.f[10]+x.f[16]*y.f[9]+x.f[17]*y.f[8]+x.f[18]*y.f[7])%mod)%mod;
        t.f[7]=((x.f[0]*y.f[7]+x.f[1]*y.f[6]+x.f[2]*y.f[5]+x.f[3]*y.f[4]+x.f[4]*y.f[3]+x.f[5]*y.f[2]+x.f[6]*y.f[1]+x.f[7]*y.f[0]+x.f[8]*y.f[18]+x.f[9]*y.f[17])%mod+(x.f[10]*y.f[16]+x.f[11]*y.f[15]+x.f[12]*y.f[14]+x.f[13]*y.f[13]+x.f[14]*y.f[12]+x.f[15]*y.f[11]+x.f[16]*y.f[10]+x.f[17]*y.f[9]+x.f[18]*y.f[8])%mod)%mod;
        t.f[8]=((x.f[0]*y.f[8]+x.f[1]*y.f[7]+x.f[2]*y.f[6]+x.f[3]*y.f[5]+x.f[4]*y.f[4]+x.f[5]*y.f[3]+x.f[6]*y.f[2]+x.f[7]*y.f[1]+x.f[8]*y.f[0]+x.f[9]*y.f[18])%mod+(x.f[10]*y.f[17]+x.f[11]*y.f[16]+x.f[12]*y.f[15]+x.f[13]*y.f[14]+x.f[14]*y.f[13]+x.f[15]*y.f[12]+x.f[16]*y.f[11]+x.f[17]*y.f[10]+x.f[18]*y.f[9])%mod)%mod;
        t.f[9]=((x.f[0]*y.f[9]+x.f[1]*y.f[8]+x.f[2]*y.f[7]+x.f[3]*y.f[6]+x.f[4]*y.f[5]+x.f[5]*y.f[4]+x.f[6]*y.f[3]+x.f[7]*y.f[2]+x.f[8]*y.f[1]+x.f[9]*y.f[0])%mod+(x.f[10]*y.f[18]+x.f[11]*y.f[17]+x.f[12]*y.f[16]+x.f[13]*y.f[15]+x.f[14]*y.f[14]+x.f[15]*y.f[13]+x.f[16]*y.f[12]+x.f[17]*y.f[11]+x.f[18]*y.f[10])%mod)%mod;
        t.f[10]=((x.f[0]*y.f[10]+x.f[1]*y.f[9]+x.f[2]*y.f[8]+x.f[3]*y.f[7]+x.f[4]*y.f[6]+x.f[5]*y.f[5]+x.f[6]*y.f[4]+x.f[7]*y.f[3]+x.f[8]*y.f[2]+x.f[9]*y.f[1])%mod+(x.f[10]*y.f[0]+x.f[11]*y.f[18]+x.f[12]*y.f[17]+x.f[13]*y.f[16]+x.f[14]*y.f[15]+x.f[15]*y.f[14]+x.f[16]*y.f[13]+x.f[17]*y.f[12]+x.f[18]*y.f[11])%mod)%mod;
        t.f[11]=((x.f[0]*y.f[11]+x.f[1]*y.f[10]+x.f[2]*y.f[9]+x.f[3]*y.f[8]+x.f[4]*y.f[7]+x.f[5]*y.f[6]+x.f[6]*y.f[5]+x.f[7]*y.f[4]+x.f[8]*y.f[3]+x.f[9]*y.f[2])%mod+(x.f[10]*y.f[1]+x.f[11]*y.f[0]+x.f[12]*y.f[18]+x.f[13]*y.f[17]+x.f[14]*y.f[16]+x.f[15]*y.f[15]+x.f[16]*y.f[14]+x.f[17]*y.f[13]+x.f[18]*y.f[12])%mod)%mod;
        t.f[12]=((x.f[0]*y.f[12]+x.f[1]*y.f[11]+x.f[2]*y.f[10]+x.f[3]*y.f[9]+x.f[4]*y.f[8]+x.f[5]*y.f[7]+x.f[6]*y.f[6]+x.f[7]*y.f[5]+x.f[8]*y.f[4]+x.f[9]*y.f[3])%mod+(x.f[10]*y.f[2]+x.f[11]*y.f[1]+x.f[12]*y.f[0]+x.f[13]*y.f[18]+x.f[14]*y.f[17]+x.f[15]*y.f[16]+x.f[16]*y.f[15]+x.f[17]*y.f[14]+x.f[18]*y.f[13])%mod)%mod;
        t.f[13]=((x.f[0]*y.f[13]+x.f[1]*y.f[12]+x.f[2]*y.f[11]+x.f[3]*y.f[10]+x.f[4]*y.f[9]+x.f[5]*y.f[8]+x.f[6]*y.f[7]+x.f[7]*y.f[6]+x.f[8]*y.f[5]+x.f[9]*y.f[4])%mod+(x.f[10]*y.f[3]+x.f[11]*y.f[2]+x.f[12]*y.f[1]+x.f[13]*y.f[0]+x.f[14]*y.f[18]+x.f[15]*y.f[17]+x.f[16]*y.f[16]+x.f[17]*y.f[15]+x.f[18]*y.f[14])%mod)%mod;
        t.f[14]=((x.f[0]*y.f[14]+x.f[1]*y.f[13]+x.f[2]*y.f[12]+x.f[3]*y.f[11]+x.f[4]*y.f[10]+x.f[5]*y.f[9]+x.f[6]*y.f[8]+x.f[7]*y.f[7]+x.f[8]*y.f[6]+x.f[9]*y.f[5])%mod+(x.f[10]*y.f[4]+x.f[11]*y.f[3]+x.f[12]*y.f[2]+x.f[13]*y.f[1]+x.f[14]*y.f[0]+x.f[15]*y.f[18]+x.f[16]*y.f[17]+x.f[17]*y.f[16]+x.f[18]*y.f[15])%mod)%mod;
        t.f[15]=((x.f[0]*y.f[15]+x.f[1]*y.f[14]+x.f[2]*y.f[13]+x.f[3]*y.f[12]+x.f[4]*y.f[11]+x.f[5]*y.f[10]+x.f[6]*y.f[9]+x.f[7]*y.f[8]+x.f[8]*y.f[7]+x.f[9]*y.f[6])%mod+(x.f[10]*y.f[5]+x.f[11]*y.f[4]+x.f[12]*y.f[3]+x.f[13]*y.f[2]+x.f[14]*y.f[1]+x.f[15]*y.f[0]+x.f[16]*y.f[18]+x.f[17]*y.f[17]+x.f[18]*y.f[16])%mod)%mod;
        t.f[16]=((x.f[0]*y.f[16]+x.f[1]*y.f[15]+x.f[2]*y.f[14]+x.f[3]*y.f[13]+x.f[4]*y.f[12]+x.f[5]*y.f[11]+x.f[6]*y.f[10]+x.f[7]*y.f[9]+x.f[8]*y.f[8]+x.f[9]*y.f[7])%mod+(x.f[10]*y.f[6]+x.f[11]*y.f[5]+x.f[12]*y.f[4]+x.f[13]*y.f[3]+x.f[14]*y.f[2]+x.f[15]*y.f[1]+x.f[16]*y.f[0]+x.f[17]*y.f[18]+x.f[18]*y.f[17])%mod)%mod;
        t.f[17]=((x.f[0]*y.f[17]+x.f[1]*y.f[16]+x.f[2]*y.f[15]+x.f[3]*y.f[14]+x.f[4]*y.f[13]+x.f[5]*y.f[12]+x.f[6]*y.f[11]+x.f[7]*y.f[10]+x.f[8]*y.f[9]+x.f[9]*y.f[8])%mod+(x.f[10]*y.f[7]+x.f[11]*y.f[6]+x.f[12]*y.f[5]+x.f[13]*y.f[4]+x.f[14]*y.f[3]+x.f[15]*y.f[2]+x.f[16]*y.f[1]+x.f[17]*y.f[0]+x.f[18]*y.f[18])%mod)%mod;
        t.f[18]=((x.f[0]*y.f[18]+x.f[1]*y.f[17]+x.f[2]*y.f[16]+x.f[3]*y.f[15]+x.f[4]*y.f[14]+x.f[5]*y.f[13]+x.f[6]*y.f[12]+x.f[7]*y.f[11]+x.f[8]*y.f[10]+x.f[9]*y.f[9])%mod+(x.f[10]*y.f[8]+x.f[11]*y.f[7]+x.f[12]*y.f[6]+x.f[13]*y.f[5]+x.f[14]*y.f[4]+x.f[15]*y.f[3]+x.f[16]*y.f[2]+x.f[17]*y.f[1]+x.f[18]*y.f[0])%mod)%mod;
    } else {
        for (int i=0;i<k;i++) for (int j=0;j<k;j++) {
            int l=i+j;
            if(l>=k)l-=k;
            t.f[l]+=x.f[i]*y.f[j]%mod;
            if(t.f[l]>=mod) t.f[l]-=mod;
        }
    }
}
void build (int l, int r, int z) {
    if (l == r) {
        for (int i = 0; i < k; i ++) a[z].f[i] = 0;
        ++ a[z].f[0]; ++ a[z].f[c[l] ];
        return;
    }
    int mid = l + r >> 1;
    build (l, mid, z << 1);
    build (mid + 1, r, z << 1 | 1);
    merge (a[z << 1], a[z << 1 | 1]);
    a[z] = t;
}
int query (int l, int r, int z) {
    if (x <= l && y >= r) {
        stack[top + 1] = a[z];
        return top + 1;
    }
    int mid = l + r >> 1, idx = ++ top;
    for (int i = 0; i < k; i ++) stack[top].f[i] = 0;
    stack[top].f[0] = 1;
    if (x <= mid) stack[top] = stack[query (l, mid, z << 1)];
    if (y > mid) {
        merge (stack[top], stack[query (mid + 1, r, z << 1 | 1)] );
        stack[top] = t;
    }
    top --;
    return idx;
}
signed main () {
    n = read ();
    q = read ();
    k = read ();
    for (int i = 1; i <= n; i ++) {
        c[i] = read ();
        c[i] -= c[i] / k * k;
    }
    build (1, n, 1);
    while (q --) {
        x = read ();
        y = read ();
        printf ("%d\n", stack[query (1, n, 1)].f[0]);
    }
    return 0;
}

加了一大堆优化，能不能过完全看脸（

真的，程序同一个点跑的最快是 300ms，最慢直接 1.1s，看来 iai 机子们有的快有的慢。

老师告诉我分治后我再写个分治做法吧。

标签：YACS,GCC,int,题解,mid,甲组,++,pragma,optimize
From： https://www.cnblogs.com/Xy-top/p/17410031.html

相关文章

  • CF1183C Computer Game 题解
    ComputerGame还算水的一道题。题意本题意为题面直接翻译的简化版，可能会比题目翻译要复杂。有\(q\)次询问，每次给出四个数，表示一开始的电亮为\(k\)，有\(n\)个回合，不插电玩一个回合则电量会减少\(a\)，插电玩一个回合则电量会减少\(b\)，电量在任何时刻都必须严格大于\(0\)......
  • Plsql或Navicat连接登陆Oracle时慢、执行语句的时候也特别慢的问题解决方案
    用Plsql或Navicat连接登陆Oracle时，等待时间特别长。经过漫长的等待后，执行语句的时候也特别慢，监听配置没毛病的情况下，大概率是监听日志文件过大导致的。监听日志路径：app\Administrator\diag\tnslsnr\LS--20171012URU\listener\trace\listener.log删除listener.log文件即可。......
  • 交通运输（Wormhole Transportaion） 题解
    传送门交通运输（WormholeTransportaion）题目大意有\(n\)个点和\(m\)个点对，你需要构造一张\(m-1\)条边的无向图，使得\(m\)个点对间最短路之和最小。求最小值及取到最小值的方案数。\(2\len\le2000,2\lenm\le2\times10^7,1\leu_i,v_i\len,u_i\neqv_i\)。......
  • P3919 【模板】可持久化线段树 1（可持久化数组） 题解
    一、题目描述：维护这样的一个长度为$n$的数组，支持以下两种操作$1$：在某个历史版本上修改某一个位置上的值$2$：访问某个历史版本上的某一位置的值每进行一次操作，就会生成一个新的版本（对于操作2，生成的就是一个完全一样的版本）。版本编号即为当前操作......
  • 题解：独占访问2 Exclusive Access 2
    题目链接怎么唯一一篇题解这么抽象，完全看不懂给定一张无向图，求给这张图定向成DAG之后的最长路最短是多少。转化一下变成对DAG进行分层，每一层之间的点没有连边，使得层数尽可能少，那么最后的层数就是答案。那么就求出若干个独立集，让独立集总数尽可能少。这是经典的色数问题，我们......
  • GYM102392 简要题解
    自己下午闲着没事单挑了一下，两小时左右一度rk1，但后继无力了。。。。A.MaxorMin肯定沿着出现过的数操作；然后发现如果a[i]=k,a[j]>k,a[k]<k就会增加一次操作所以维护一下差分序列即可。B.LevelUp两维DP，这个疑似edu出过。要注意的是：需要关于x排个序，不然会漏一些转移。D.......
  • AT_dp_s 题解
    题目传送门第一道数位\(\text{dp}\)，检验一下自己懂没懂。特别感谢\(\text{yinhee}\)大佬，他的讲解令我受益匪浅。题目分析\(dp_{pos,res,lim}\)为当前枚举到从高位往低位数第\(pos\)位，数字和取模后的余数为\(res\)时的方案数，其中\(lim\)可以理解为一个布尔值，\(0\)表......
  • abc260_g Scalene Triangle Area 题解
    题目传送门题意给定一个大小为\(n\timesn\)的字符矩阵，每个字符为X或者O。对于一个位于\((x,y)\)的字符o和一个格子\((u,v)\)，如果满足以下条件，那么\((u,v)\)就可以被\((x,y)\)控制。\(x\leqslantu\leqslantn\)，\(y\leqslantv\leqslantn\)。\((u-x)+\fr......
  • 前端传递参数与后端接收的类属性不一致问题解决办法
    使用@JsonAlias作用是在反序列化的时候可以让Bean的属性接收多个json字段的名称。可以加在字段上或者getter和setter方法上。publicclassUser{ @JsonAlias({"name","user"}) privateStringusername; privateStringpassword; privateIntegerage;}这样子......
  • JOISC 2018 题解
    没做计算几何题和提交答案题。JOISC2018Day1ConstructionofHighway道路建设注意到题目中的操作相当于就是到根的路径染色，我们离线下来进行树剖，每条重链维护连续段，然后显然均摊会修改\(O(n\logn)\)段。我们每次修改时可以取出所有连续段，然后题目问逆序对数，我们对这些连续......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99