不知道如何评价题。
题意：
给出两个数 ，构造序列 ，使其满足下列限制：
。
。
是 的倍数。
在此基础上，使得
最小，输出答案对
取模的值。
组数据。。
显然，策略是让每个
都尽量小。
那么设 ，就有
因为 约等于 ，设 ，那么会有 。
那么可以说明，在 的时候，。
也就是说， 只有 个本质不同的值！
因为这玩意单调不增，所以最终会呈现若干个连续段。
然后我想到这里不会算端点！
考虑一个 ，设 ，我们想求出最大的
满足
化式子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
const int P = 998244353,inv2 = (P + 1) / 2,inv6 = 166374059;
typedef long long ll;
ll n,nowb;
inline ll cdiv(ll x,ll y) { return (x + y - 1) / y;}
inline int S1(ll x) { x %= P;return 1ll * x * (x + 1) % P * inv2 % P;}
inline int S2(ll x) { x %= P;return 1ll * x * (x + 1) % P * (2 * x + 1) % P * inv6 % P;}
inline int calc(ll fr,ll d,ll l,ll r)
{
int res1 = 1ll * (fr % P) * (S1(r) - S1(l - 1) + P) % P;
int res2 = 1ll * (d % P) * (S2(r) - S2(l - 1) + P) % P;
int res3 = 1ll * (l % P) * (d % P) % P * (S1(r) - S1(l - 1) + P) % P;
return (1ll * res1 + res2 - res3 + P) % P;
}
inline void Work()
{
cin >> n >> nowb;
int ans = 0;
for(ll l = 1,r;l <= n;l = r + 1)
{
ll x = cdiv(nowb,l + 1);
if(x == 1) r = n;
else r = min(n,(nowb + (l + 1) * (x - 1) - 1) / (2 * x - 2) - 1);
(ans += calc(nowb,1 - x,l,r)) %= P;
nowb -= (r - l + 1) * (x - 1);
}
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while(T--) Work();
return 0;
}
|
事实上，上文中的 " 约等于
" 是可以严谨的给出一个
上界的。
因为
所以 。
设 。
由此可以算出 处于
级别，即在 的时候， 的取值也只有 个。
于是总段数就是 的了。