ZOJ 3940 - Modulo Query

题意：

F(1, x) = x \mod A_1 \\ F(i, x) = F(i - 1, x) \mod A_i

给出A[]，求不大于M的使得F(n, x) = Y 的X的个数

思路：

https://blog.csdn.net/jk_chen_acmer/article/details/108025252

区间取模，每次取模相当于把一个大的区间变成两个小的区间，[0, R1] -> [0, mod - 1] && [0, R1 % mod - 1]，可以用map处理

用map记录下[ 0 , R ]的个数num

每次模上mod时，在map里面把所有 $\geq mod$ 的区间（lower_bound）操作一遍即可。

最后统计答案的时候对所有Y 排序，因为 $R \geq Y$ 的区间都会对Y有贡献，所以统计也很简单。

时间复杂度：

拆分后的区间对下一次拆分的有效次数都不会超过log次，（极限情况是/2)

code

#include 
   
    #include 
    
     #include 
     using namespace std;typedef long long ll;const int N = 1e5 + 10;const ll mod = 1e9 + 7;ll a[N];struct node {       ll x, id;} qus[N];map
      
        mp;int main() {       int T;    cin >> T;    while (T--) {           ll n, m;        cin >> n >> m;        mp.clear();        mp.insert({   m, 1});        for (int i = 1; i <= n; ++i) {               cin >> a[i];            auto it = mp.lower_bound(a[i] - 1);            if (it == mp.end()) continue;            while (it != mp.end()) {                   ll r = (*it).first;                ll num = (*it).second;                mp.erase(it++);//                it++;                ll k = (r + 1) / a[i];                mp[a[i] - 1] = (mp[a[i] - 1] + (k * num) % mod) % mod;                if ((r + 1) % a[i] != 0) {                       ll tmp = (r + 1) % a[i];                    mp[tmp - 1] = (mp[tmp - 1] + num) % mod;                }            }        }//        cout << " ok here" << endl;        ll q;        cin >> q;        for (int i = 1; i <= q; ++i) {               cin >> qus[i].x;            qus[i].id = i;        }        sort(qus + 1, qus + q + 1, [](node a, node b) {    return a.x > b.x; });        ll ans = 0, sum = 0;        auto it = mp.end();        it--;        bool flag = 0;        for (int i = 1; i <= q; ++i) {               while (!flag) {                   ll r = it->first;                ll num = it->second;                if (r >= qus[i].x) {                       sum = (sum + num) % mod;                    if (it == mp.begin()) {                           flag = 1;                        break;                    }                    it--;                } else {                       break;                }            }            ans = (ans + sum * qus[i].id) % mod;        }        cout << ans << endl;    }    return 0;}

中间遇到了一个问题// 待解决，这两天要搞懂…*

这样是对的：

mp.erase(it++);//it++;

这样会报错：

mp.erase(it);it++;

upd：

替换成 it = mp.erase(it);

// 删除元素后，后面元素自动往前移，不用挪动指针

再upd ：（问懂了之后专门写了一个blog//）

https://blog.csdn.net/qq_39602052/article/details/115522409

上一篇：关于erase的一个奇bai怪chi问题

下一篇：D - Competition Against a Robot //2020icpc kunming

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

ZOJ 3940 - Modulo Query

发表评论

最新留言

关于作者

推荐文章