首页 > 其他分享 >Diary - 2024.12.26

Diary - 2024.12.26

时间：2024-12-26 22:31:29浏览次数：2  
标签：2024.12 26 int ll constexpr Diary 卡常 Sum mod

今天作业量似乎更多了。
或许老师认为我们做完作业后都还有很多时间吧！

不是我真的红温了。

Luogu P11420 [清华集训 2024] 乘积的期望。

我今天搞了一天的这玩意，写到最后被卡常了，卡了 2h 没进去。
我玉玉了。我玉玉了。我玉玉了。我玉玉了。我玉玉了。我玉玉了。

现在成就是 Luogu TLE on #75, #76, #106, #107，额额。
为什么机房的机子上跑 #75 2.1s，Luogu > 2.2s, QOJ = 2.6s。
？？？

怎么机房机子这么快？？？

有没有人帮我卡卡常阿，有没有人帮我卡卡常阿，有没有人帮我卡卡常阿，有没有人帮我卡卡常阿，有没有人帮我卡卡常阿，有没有人帮我卡卡常阿，

我现在的代码已经抽象到了：

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
inline void add(ll &x, ll y) {
   (x += y) >= mod && (x -= mod);
}
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b) {
      if (b & 1) ((v *= a) %= mod);
      b >>= 1, (a *= a) %= mod;
   }
   return v;
}
constexpr int maxn = 150 + 5, maxm = 50 + 2;
int n, m, C;
ll b[maxn], S;
ll res = 1ll;
namespace solve1 {
   constexpr int maxm = 16;
   inline ll Sum(int l, int r) {
      return l <= 0 ? b[r] : ((b[r] - b[l - 1] + mod) % mod);
   }
   ll f[maxn][1 << maxm - 1], g[maxn][1 << maxm - 1];
   inline ll solve() {
      if (m == 1) {
         if (C < n) return 0ll;
         ll ans = 1ll;
         for (int i = 1; i <= n; i++) (ans *= C - i + 1) %= mod;
         for (int i = 1; i <= n; i++) (ans *= b[i]) %= mod;
         return ans;
      }
      for (int i = 1; i <= n; i++) (b[i] += b[i - 1]) %= mod;
      f[0][0] = 1;
      for (int i = 1; i <= n; i++) {
         for (int c = 0; c < i; c++) {
            for (int s = 0; s < (1 << m - 1); s++) {
               g[c][s] = f[c][s], f[c][s] = 0ll;
            }
         }
         for (int c = 0; c < i; c++) {
            for (int s = 0; s < (1 << m - 1); s++) {
               if (~ s & 1) {
                  (f[c + 1][s >> 1] += g[c][s] * Sum(i - m + 1, i)) %= mod;
                  (f[c][s >> 1] += g[c][s] * __builtin_popcount(s)) %= mod;
                  (f[c + 1][(s | (1 << m - 1)) >> 1] += g[c][s]) %= mod;
                  for (int w = 1; w < m - 1; w++) {
                     if (s >> w & 1) {
                        (f[c][(s ^ (1 << w)) >> 1] += g[c][s] * Sum(i - m + 1, i - m + 1 + w)) %= mod;
                     }
                  }
               } else {
                  (f[c][s >> 1] += g[c][s] * Sum(i - m + 1, i - m + 1)) %= mod;
               }
            }
         }
      }
      ll ans = 0ll, A = 1ll;
      for (int i = 1; i <= std::min(n, C); i++) {
         (A *= C - i + 1) %= mod;
         (ans += A * f[i][0]) %= mod;
      }
      return ans;
   }
}
namespace solve2 {
   ll f[maxm][maxm], g[maxm][maxm], pw1[maxm], pwm[maxm];
   constexpr ll fac[maxm] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 237554682, 331032489, 972509923, 586493473, 986189864, 781263551, 868586527, 401576539, 447152495, 853155713, 655938692, 768863313, 254940118, 638976950, 282223649, 914551701, 567646151, 59230529, 837902046, 858512294, 380063818, 943237576, 71251511, 568565690, 73799117, 807877740, 561656917, 504900914, 736050414, 966786798, 643813841, 376967120, 991610752, 693098707, 631819933, 380026194, 652885152, 700438304};
   constexpr ll ifac[maxm] = {1, 1, 499122177, 166374059, 291154603, 856826403, 641926577, 376916469, 421456191, 712324701, 370705776, 305948985, 275056837, 405098354, 314148269, 154042465, 945481735, 407938109, 632701444, 33300076, 400962745, 637054254, 664203418, 419495765, 475007652, 657876692, 178879004, 856981449, 707986577, 403057740, 13435258, 676663441, 489072773, 529067478, 837644393, 280624102, 285085212, 574276125, 724391412, 632878356, 714593006, 845241488, 352872915, 936805745, 996848021, 199617841, 416657838, 454889133, 71867129, 470030352, 328838800};
   inline ll calc() {
      ll ans = 0ll;
      for (int c2 = 0; c2 <= C; ++c2) {
         auto clr = [&](int hk) {
            for (int j = 1; j + c2 <= C; ++j) {
               for (int k = 0; k <= hk; ++k) {
                  g[j][k] = f[j][k], f[j][k] = 0;
               }
            }
         };
         clr(c2);
         for (int i = 1; i + c2 <= C; ++i) {
            f[i][c2] = pw1[i] * ifac[i] % mod * i * (C - i - c2) * (m + m + 1 <= n ? c2 : 1ll) % mod;
         }
         for (int i = 1; i < m; ++i) {
            int hk = m + m + i <= n ? c2 : 0;
            clr(hk);
            for (int j = 1; j + c2 <= C; ++j) {
               for (int k = 0; k <= hk; ++k) {
                  ll val_ = g[j][k];
                  for (int nj = j; nj + c2 <= C; ++nj, (val_ *= b[i + 1]) %= mod) {
                     ll val = val_ * ifac[nj - j] % mod * nj % mod;
                     for (int nk = k; ~ nk; --nk, (val *= b[m + i + 1]) %= mod) {
                        add(f[nj][nk], val * ifac[k - nk] % mod * (C - nj - nk) * (m + m + i + 1 <= n ? nk : 1ll) % mod);
                     }
                  }
               }
            }
         }
         for (int j = 1; j + c2 <= C; j++) {
            ll val = f[j][0];
            (val *= pwm[C - j - c2] * ifac[C - j - c2] % mod) %= mod;
            (ans += val) %= mod;
         }
      }
      return ans * fac[C] % mod;
   }
   inline ll solve() {
      for (int j = pw1[0] = pwm[0] = 1; j <= n; j++) {
         pw1[j] = pw1[j - 1] * b[1] % mod, pwm[j] = pwm[j - 1] * b[m + 1] % mod;
      }
      int C_ = C;
      ll ans = 0;
      for (C = 1; C <= n; C++) {
         ll val = calc();
         for (int i = 0; i <= n; i++) {
            if (i == C) continue;
            (val *= qpow((C - i + mod) % mod, mod - 2) * (C_ - i + mod) % mod) %= mod;
         }
         (ans += val) %= mod;
      }
      return ans;
   }
}
int main() {
   scanf("%d%d%d", &n, &m, &C);
   for (int i = 1; i <= n - m + 1; i++) scanf("%lld", &b[i]);
   for (int i = 1; i <= n - m + 1; i++) (S += b[i]) %= mod;
   S = qpow(S, mod - 2);
   for (int i = 1; i <= n - m + 1; i++) (b[i] *= S) %= mod;
   if (m * 2 > n) {
      int l = m * 2 - n;
      res = qpow(C, l);
      m -= l, n -= l;
   }
   printf("%lld\n", (m <= 16 ? solve1::solve() : solve2::solve()) * res % mod);
   return 0;
}

最初始的代码：

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
inline void add(ll &x, ll y) {
   (x += y) >= mod && (x -= mod);
}
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b) {
      if (b & 1) ((v *= a) %= mod);
      b >>= 1, (a *= a) %= mod;
   }
   return v;
}
constexpr int maxn = 150 + 5, maxm = 50 + 2;
int n, m, C;
ll b[maxn], S;
ll res = 1ll;
namespace solve1 {
   constexpr int maxm = 16;
   inline ll Sum(int l, int r) {
      return l <= 0 ? b[r] : ((b[r] - b[l - 1] + mod) % mod);
   }
   ll f[maxn][1 << maxm - 1], g[maxn][1 << maxm - 1];
   inline ll solve() {
      if (m == 1) {
         if (C < n) return 0ll;
         ll ans = 1ll;
         for (int i = 1; i <= n; i++) (ans *= C - i + 1) %= mod;
         for (int i = 1; i <= n; i++) (ans *= b[i]) %= mod;
         return ans;
      }
      for (int i = 1; i <= n; i++) (b[i] += b[i - 1]) %= mod;
      f[0][0] = 1;
      for (int i = 1; i <= n; i++) {
         for (int c = 0; c < i; c++) {
            for (int s = 0; s < (1 << m - 1); s++) {
               g[c][s] = f[c][s], f[c][s] = 0ll;
            }
         }
         for (int c = 0; c < i; c++) {
            for (int s = 0; s < (1 << m - 1); s++) {
               if (~ s & 1) {
                  (f[c + 1][s >> 1] += g[c][s] * Sum(i - m + 1, i)) %= mod;
                  (f[c][s >> 1] += g[c][s] * __builtin_popcount(s)) %= mod;
                  (f[c + 1][(s | (1 << m - 1)) >> 1] += g[c][s]) %= mod;
                  for (int w = 1; w < m - 1; w++) {
                     if (s >> w & 1) {
                        (f[c][(s ^ (1 << w)) >> 1] += g[c][s] * Sum(i - m + 1, i - m + 1 + w)) %= mod;
                     }
                  }
               } else {
                  (f[c][s >> 1] += g[c][s] * Sum(i - m + 1, i - m + 1)) %= mod;
               }
            }
         }
      }
      ll ans = 0ll, A = 1ll;
      for (int i = 1; i <= std::min(n, C); i++) {
         (A *= C - i + 1) %= mod;
         (ans += A * f[i][0]) %= mod;
      }
      return ans;
   }
}
namespace solve2 {
   ll f[maxm][maxm], g[maxm][maxm], pw[maxn][maxm], fac[maxn], ifac[maxm];
   inline ll calc() {
      ll ans = 0ll;
      for (int c2 = 0; c2 <= C; c2++) {
         memset(f, 0, sizeof(f));
         for (int i = 0; i + c2 <= C; i++) {
            f[i][c2] = pw[1][i] * ifac[i] % mod;
            if (1 <= n) (f[i][c2] *= i) %= mod;
            if (m + 1 <= n) (f[i][c2] *= C - i - c2) %= mod;
            if (m + m + 1 <= n) (f[i][c2] *= c2) %= mod;
         }
         for (int i = 1; i < m; i++) {
            memcpy(g, f, sizeof(g));
            memset(f, 0, sizeof(f));
            for (int j = 0; j + c2 <= C; j++) {
               for (int k = 0; k <= c2; k++) {
                  for (int nj = j; nj + c2 <= C; nj++) {
                     for (int nk = 0; nk <= k; nk++) {
                        ll val = g[j][k];
                        (val *= pw[i + 1][nj - j] * pw[m + i + 1][k - nk] % mod) %= mod;
                        (val *= ifac[nj - j] * ifac[k - nk] % mod) %= mod;
                        if (i + 1 <= n) (val *= nj) %= mod;
                        if (m + i + 1 <= n) (val *= C - nj - nk) %= mod;
                        if (m + m + i + 1 <= n) (val *= nk) %= mod;
                        (f[nj][nk] += val) %= mod;
                     }
                  }
               }
            }
         }
         for (int j = 0; j + c2 <= C; j++) {
            ll val = f[j][0];
            (val *= pw[m + 1][C - j - c2] * ifac[C - j - c2] % mod) %= mod;
            (ans += val) %= mod;
         }
      }
      return ans * fac[C] % mod;
   }
   inline ll solve() {
      for (int i = fac[0] = 1; i <= n + 1; i++) fac[i] = fac[i - 1] * i % mod;
      for (int i = 0; i <= n + 1; i++) ifac[i] = qpow(fac[i], mod - 2);
      for (int i = 1; i <= m * 3; i++) {
         for (int j = pw[i][0] = 1; j <= n + 1; j++) {
            pw[i][j] = pw[i][j - 1] * b[i] % mod;
         }
      }
      int C_ = C;
      ll ans = 0;
      for (C = 0; C <= n + 1; C++) {
         ll val = calc();
         for (int i = 0; i <= n + 1; i++) {
            if (i == C) continue;
            (val *= qpow((C - i + mod) % mod, mod - 2) * (C_ - i + mod) % mod) %= mod;
         }
         (ans += val) %= mod;
      }
      return ans;
   }
}
int main() {
   scanf("%d%d%d", &n, &m, &C);
   for (int i = 1; i <= n - m + 1; i++) scanf("%lld", &b[i]);
   for (int i = 1; i <= n - m + 1; i++) (S += b[i]) %= mod;
   S = qpow(S, mod - 2);
   for (int i = 1; i <= n - m + 1; i++) (b[i] *= S) %= mod;
   if (m * 2 > n) {
      int l = m * 2 - n;
      res = qpow(C, l);
      m -= l, n -= l;
   }
   printf("%lld\n", (m <= 16 ? solve1::solve() : solve2::solve()) * res % mod);
   return 0;
}

可见抽象。

从 > 4s 卡到了 2.1s 还是过不了，愤怒了愤怒了愤怒了愤怒了愤怒了愤怒了愤怒了愤怒了愤怒了。

被卡常注定只能度过一个失败的 oi 生涯。
被卡常注定只能度过一个失败的 oi 生涯。
被卡常注定只能度过一个失败的 oi 生涯。
被卡常注定只能度过一个失败的 oi 生涯。
被卡常注定只能度过一个失败的 oi 生涯。

明天必须卡完常再写其他题/fn。
明天必须卡完常再写其他题/fn。
明天必须卡完常再写其他题/fn。
明天必须卡完常再写其他题/fn。
明天必须卡完常再写其他题/fn。

怎么要期末了？？？
感觉时间好快的过，这个学年又过了一半了。
相比之下，我学会了什么呢？？？

应该以后就能看出来了吧！

有点困有点困有点困有点困有点困有点困有点困。
其实感觉我每天睡眠问题也不是很大阿？？？
但是比较神秘的是每天上课会在差不多固定的时间犯困。

但是好像班上同学都会这样，是不是透气原因（？）。

这几天的晚霞一直是粉紫粉紫的，很好看。

但是没有时间了，明天看看晚霞再继续沿着这个话题写。

今天我的水杯突然失踪了？？？
希望在宿舍，毕竟其他地方都找了。

发现昨天的日记日期写成了 2024.12.24，好的改了。

标签：2024.12,26,int,ll,constexpr,Diary,卡常,Sum,mod
From： https://www.cnblogs.com/rizynvu/p/18634299

相关文章

  • 最新版软件著作权申请流程【2024.12】
    最近刚刚给大创的软件申请了软件著作权，在这里分享一下经验。一、软著平台上注册所有著作人都需要在中国版权保护中心上面完成注册以及实名认证，实名认证大概需要3-4个工作日。二、平台上资料的提交1.点击版权登记的软件登记，选择计算机软件著作权登记申请。2.点击我是申......
  • 2024/12/26
    「省选联考2023」城市建造考虑选出\(t\)个点，每个连通块选出恰好一个点。注意到在同一个点双里的点要么同时被选出要么全部都不选。建圆方树，选出一个方点就代表选出了所有其代表的点双上的所有圆点。有一个性质：所有被选中的方点是连通的。否则一个连通块必定存在两个点被选......
  • 12.26日每日总结
    昨天在调试51单片机的串口时，发现芯片手册上有一句话，在使用定时器1产生串口的波特率时，定时器1就不能使能了。不是不能用，是直接不让使能了，使能后会出错，导致发送的数据不稳定。今天继续研究了触摸滑条，发现滑条输出的值为从小到大，如下图所示的样子，这就导致从最上面滑动向下滑动和中间......
  • 12.26
    11、创建配置文件jdbc.properties23jdbc.driver=com.mysql.jdbc.Driver4jdbc.url=jdbc:mysql://localhost:3306/shop5jdbc.username=root67jdbc.password=123456892、读取配置文件类1011packagecom.hx.shopping.util;1213importjava.io.IOException;1415......
  • 9.26
    今天完成数据库表。1.1  工人管理表（Users）字段类型Null默认注释Idint否 自增长主键usernamevarchar(8)否 工人工号 唯一键Passwordvarchar(255)否 工号密码Namevarchar(100)否 工......
  • 2024年12月26日Github流行趋势
    项目名称：project-based-learning项目维护者：@tuvtran,@sayands,@enkeyz,@bobeff,@olucode项目介绍：精选的基于项目的教程列表。项目star数：208,918项目fork数：27,266项目名称：system-design-primer项目维护者：@donnemartin,@cclauss,@satob,@fluency03,@linhe0x0项目......
  • LeetCode 2605 从两个数字数组里生成最小数字
    探寻两个数组数位关联下的最小数字问题题目描述给定两个只包含1到9之间数字的数组 nums1 和 nums2，并且每个数组中的元素都是互不相同的。我们需要返回最小的数字，要求这个数字满足两个数组都至少包含这个数字的某个数位。例如，若 nums1=[4,1,3]，nums2=[5,7]，那么......
  • 2024.12.26 考试总结
    \(55+42+50=147,rk2\)。T1序列直接上吉司机线段树，特判\(+\0\)情况即可。我猜测时间复杂度是\(O(n\log^2n)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=4e5+5;intn,m,mn[N],nn[N],ad[N];intadn[N],chg[N],chgn[N];voidpu......
  • 12.26 CW 模拟赛 T1. 平均
    思路首先你发现假设当前的平均数是\(a\),其中\(\lceila\rceil=k\),那么你势必要选上所有\(<k\)的数来拉低平均数,然后贪心的从小到大选\(\geqk\)的数来提高贡献如果想不到也可以这样想,对于一个确定的平均数,一定要尽可能的让比平均数小的数更多,才能更多的......
  • CW 12.26 模拟赛 赛时记录
    前言虽然说有点难受,但是还是好好考考试只需要管考试相关的即可,别想太多冷静,就这样看题先过一遍吧,看看感觉怎么样,今天时间要短一点,不开心\(\rm{T1}\)至少题意清楚,不管了\(\rm{T2}\)这么有实力,很像\(\rm{Indec\Sequence}\)\(\rm{T3}\)多半要观察性质......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99