「模拟赛20180307」三元组 exclaim 枚举+树状数组
题目描述
给定 $n,k$ ,求有多少个三元组 $(a,b,c)$ 满足 $1≤a≤b≤c≤n$且$a + b^2 ≡ c^3\ (mod\ k)$。
输入
多组数据,第一行数据组数$T$。
每组数据两个整数,$n$和$k$。
输出
$T$行,每行一个整数,表示满足条件的三元组的个数。
样例输入
1
10 7
样例输出
27
数据范围
$1≤n,k≤10^5$
$T≤400$
时间限制$4s$
题解
与其他学校互测,然后做题感觉很不友好……
这道题数据很有特点(哪里很有特点了),$10^5$显然是一个象征性的数字,它意味着$O(n\ log\ n)$是可以过的(这么大的$T$被无视了啊)。
那么很自然的想到,这个式子并没有什么规律(我也很无奈啊),我们可以考虑枚举$a,b,c$中的$1$个。
但是我们选择哪一个比较好呢?容易想到,应该是$c$,它的次数最高,不易计算。
接下来考虑一个简化的问题,如果不取余$k$,该怎么办?
对于一个数$b$,由于$1≤a≤b$,显然$c^3$只有在$[b^2+1,b^2+b]$范围内才有解,而且是唯一解。
所以每一个$b$可以为在$[b^2+1,b^2+b]$的$c^3$提供一个解,这不就是区间增加一个值吗?树状数组即可做到
再考虑取余$k$时,发现情况如出一辙,一样的做就可以了。唯一一个问题就是,$[b^2+1,b^2+b]$可能长度超过了$k$。
这时能发现长度超过$k$后完全覆盖了所有区域,任何一个$c$都可以使用这个$b$,我们只需要一个计数器$count$,每次增加$\left \lfloor\frac{b}{k}\right \rfloor$。
现在,这道题的解法就呼之欲出了。我们从小到大枚举$c$,先在树状数组$(tree)$中$[c^2+1,c^2+c]$的区间加上$1$,并更新$count$,答案就等于$tree[c^3\%k]+count$。时间复杂度为$O(Tn\ log\ n)$(再说一次请无视$T$的大小)
$Code:$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define N 100005 #define ll long long int T, n, mod; ll ans, now, t[N]; void update(int x, int v) { for (int i = x; i <= mod; i += i & -i) t[i] += v; } ll getsum(int x) { ll ans = 0; for (int i = x; i; i -= i & -i) ans += t[i]; return ans; } int main() { freopen("exclaim.in", "r", stdin); freopen("exclaim.out", "w", stdout); scanf("%d", &T); for (int cas = 1; cas <= T; cas++) { scanf("%d%d", &n, &mod); ans = now = 0; memset(t, 0, sizeof(t)); for (int i = 1; i <= n; i++) { int l =(1ll * i * i + 1)% mod + 1, r =(1ll * i * i + i)% mod + 1; if (l <= r) update(l, 1), update(r + 1, -1); else update(1, 1), update(r + 1, -1), update(l, 1); int c = 1ll * i * i % mod * i % mod; now +=(i - 1)/ mod; ans += getsum(c + 1) + now; } printf("Case %d: ", cas); cout << ans; putchar(10); } }
最后的吐槽:$exclaim$并不是三元组的意思,是惊叫的意思……至于为什么,我也不知道……