戳感牢磁简单题直接将区间求和转换成前缀和设 \(A_i \sum_{i 1}^n a_i,B_i \sum_{i 1}^n b_i\)那么式子为\[\sum_{l 1}^n \sum_{r l}^n (A_r-A_{l-1})(B_r-B_{l-1}) \]\[\sum_{l 1}^n \sum_{r l}^n A_rB_r-A_rB_{l-1}-A_{l-1}B_rA_{l-1}B_{l-1} \]很明显 \(O(n)\) 枚举右端点 \(r\)式子变成\[\sum_{l 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_rA_{l-1}B_{l-1} \]如何快速算出这个式子我们有\[\sum_{l 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_rA_{l-1}B_{l-1}\sum_{l 1}^r A_rB_r-\sum_{l 1}^r A_rB_{l-1}-\sum_{l 1}^r A_{l-1}B_r\sum_{l 1}^r A_{l-1}B_{l-1} \]于是可以将四个单项式分类讨论。\(A_rB_r\) 很好处理直接算由于 \(l\) 有 \(r\) 个取值所以是 \(rA_rB_r\)。\(A_rB_{l-1}\) 很明显 \(A_r\) 没有问题但 \(B_{l-1}\) 需要预处理 \(B\) 的前缀和也就是前缀和的前缀和。\(A_{l-1}B_r\) 同理。\(A_{l-1}B_{l-1}\) 很显然需要另外维护两前缀和之积的前缀和。代码#includeusing namespace std;const int mod 1e97;const int N 5e55;int a[N],b[N];long long suma[N],sumb[N],prea[N],preb[N],mul[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin n;for(int i 1;in;i){cin a[i];suma[i] (suma[i-1]a[i])%mod;prea[i] (prea[i-1]suma[i])%mod;}for(int i 1;in;i){cin b[i];sumb[i] (sumb[i-1]b[i])%mod;preb[i] (preb[i-1]sumb[i])%mod;mul[i] (mul[i-1]1ll*suma[i]*sumb[i]%mod)%mod;}long long sum 0;for(int i 1;in;i){long long A i*suma[i]%mod*sumb[i]%mod,B suma[i]%mod*preb[i-1]%mod,C sumb[i]%mod*prea[i-1]%mod,D mul[i-1];sum (sum(((A-Bmod)%mod-Cmod)%modD)%mod)%mod;}cout sum;return 0;}P8557 炼金术Alchemy对于每一个金属它会被任意 \(1 \sim k\) 个熔炉炼烧出来所以方案数为 \(C_k^1C_k^2C_k^3\dotsC_k^{k-1}C_k^k \sum_{i 1}^k C_k^i\)根据二项式定理\((11)^k \sum_{i 0}^k C_k^ix^i y^{n-i} \sum_{i 0}^k C_k^i\)而 \(C_k^0 1\)所以 \(\sum_{i 1}^k C_k^i 2^k-1\)那么有 \(n\) 个金属答案就是 \((2^k-1)^n\)快速幂计算即可。代码#includeusing namespace std;const int mod 998244353;int fast_pow(int a,int b){int ans 1;while(b){if(b1){ans 1ll*ans*a%mod;}a 1ll*a*a%mod;b1;}return ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,k;cin n k;cout fast_pow((fast_pow(2,k)-1mod)%mod,n);return 0;}P6191 [USACO09FEB] Bulls And Cows S这题我根本不是用数学方式做的。递推设 \(fg_i\) 表示第 \(i\) 头是公牛时的方案数\(fn_i\) 表示第 \(i\) 头是奶牛时的方案数则状态转移方程为\[fn_i fn_{i-1}fg_{i-1} \]\[fg_i fg_{i-k-1}fn_{i-k-1}(ik1) \]\[fg_i 1(i \le k1) \]迎刃而解。代码#includeusing namespace std;const int mod 5000011;const int N 1e55;int a[N];int fn[N],fg[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,k;cin n k;fn[1] 1;fg[1] 1;for(int i 2;in;i){fn[i] (fn[i-1]fg[i-1])%mod;if(ik1){fg[i] (fg[i-k-1]fn[i-k-1])%mod;}else{fg[i] 1;}}cout (fn[n]fg[n])%mod;return 0;}P8183 [USACO22FEB] Sleeping in Class B首先不管怎么合并最后数组中所有数的和都是一样的所以可以算出总和 \(sum\)然后找到 \(sum\) 的所有约数从小到大排个序由于每次合并数组长度减少 \(1\)所以我们知道拿原本数组长度减去合并后的数组长度就是合并的次数那我们肯定使长度越大越好由于约数已经倒序排序形成数组 \(b\)我们倒着扫将 \(b_i\) 看成长度那么 \(\frac{sum}{b_i}\) 就是最终合并之后数组中统一的数然后扫一遍原数组 \(a\) 检测一下即可。时间复杂度 \(O(n\sqrt{n})\)。代码#includeusing namespace std;const int N 1e65;int a[N];int ans[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _;cin _;while(_--){int n,sum 0,cnt 0,biao 1;cin n;for(int i 1;in;i){cin a[i];suma[i];if(i1a[i]!a[i-1]){biao 0;}}if(biao){cout 0 \n;}for(int i 1;i*isumin;i){if(sum%i 0){ans[cnt] i;int s sum/i;if(s!isn){ans[cnt] s;}}}sort(ans1,anscnt1);for(int i cnt;i;--i){int num sum/ans[i];int summ 0;int flag 1;int res 0;for(int j 1;jn;j){if(summa[j]num){summa[j];}else{flag 0;break;}if(summ num){res;summ 0;}}if(flagres ans[i]){cout n-ans[i] \n;break;}}}return 0;}-P10411 「QFOI R2」树色尤含残雨首先根据唯一分解定理可得\[x \prod_{i 1}^k p_i^{q_i},p_i \in prime,q_i \in N^ \]然后分类讨论首先你会发现当 \(x\) 有因子是完全平方数也就是分解之后 \(\exists i(1 \le i \le n)q_i1\)那么答案除了在只有一个质因数的时候为 \(x\) 其他情况都是 \(1\)不分奇偶为啥很简单因为就算质因子数量为奇数也可以将其中一个拆分变成偶数。那么如果 \(x\) 没有因子是完全平方数那么就要看奇偶了奇数就取最小质因数简单贪心思想偶数就是 \(1\)原理简单不再敖述。代码#includeusing namespace std;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,minn 0,num 0,shu 0;cin n;int q n;for(int i 2;i*in;i){if(n%i 0){if(!minn){minn i;}num;int cnt 0;while(n%i 0){cnt;n/i;}if(cnt1){shu;}}}if(n1){if(!minn){minn n;}num;}if(!shu){if(num1){cout minn;}else{cout 1;}}else{if(num 1){cout q;}else{cout 1;}}return 0;}P9148 除法题很显然题目的数据范围 \(n \le 5 \times 10^3\)复杂度显然是 \(O(n^2)\) 或者 \(O(n^2 \log n)\)很显然这题是数学题时限又如此之大很明显能猜出复杂度为 \(O(n^2 \log n)\) 级别而说到 \(\log\) 在数学中很容易想到调和级数那么这题就很显然了题目要求的东西是\[\sum_{a \in A}\sum_{b \in A}\sum_{c \in A}\lfloor \frac{a}{b}\rfloor\lfloor \frac{a}{c}\rfloor\lfloor \frac{b}{c}\rfloor \]很显然只有在 \(abc\) 的时候有贡献那么考虑枚举枚举 \(b,c\)复杂度 \(O(n^2)\)然后充分利用调和级数枚举 \(s\) 表示 \(\lfloor\frac{a}{c}\rfloor\) 那么 \(a\) 能取的合法值就是一个区间记这个区间为 \([l,r]\)假设能 \(O(1)\) 计算 \([l,r]\) 的值域中 \(\lfloor\frac{a}{b}\rfloor\) 的和那么迎刃而解复杂度为 \(O(n^2 \log n)\)然而 \(O(1)\) 处理这个区间的贡献很容易前缀和预处理即可。那么最后要求的其实就是\[\sum_{b \in A}\sum_{c \in A}\lfloor\frac{b}{c}\rfloor\sum_{s 1}^{\frac{max_{i 1}^n A_i}{c}}s\sum_{a \in A,l \le a \le r}\lfloor\frac{a}{b}\rfloor \]\(l\) 和 \(r\) 的赋值写不下了放这里\[l \max(b1,s \times c) \]\[r \min(\max_{i 1}^n A_i,(s1) \times c-1) \]然后还要注意三点首先 \(l\) 和 \(r\) 是值域而并非下标而前缀和很明显不能太方便地维护值域所以要将 \(l,r\) 转化成下标最好预处理解决。在算出 \(l\) 的时候记得特判一下 \(l\max_{i 1}^nA_i\) 的情况和换算成下标后的 \(lr\) 的可能性我也不确定第二个要不要判但判一下总没错并且第一个是一定要判的。\(l,r\) 的转下标方式不一样一个是 lower_bound一个是 upper_bound。代码#includeusing namespace std;const int N 5e35;const long long mod 1ll32;int b[N],pre[N][N],c[N],a[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,maxx 0;cin n;for(int i 1;in;i){cin a[i];maxx max(maxx,a[i]);}sort(a1,an1);for(int i 1;in;i){for(int j 1;jmaxx;j){pre[i][j] pre[i-1][j]a[i]/j;}}for(int i 1;imaxx;i){b[i] lower_bound(a1,an1,i)-a;c[i] upper_bound(a1,an1,i)-a-1;}long long ans 0;for(int i 1;in;i){for(int j 1;j{int cc a[i]/a[j];int MAX maxx/a[j];long long sum 0;for(int k 1;kMAX;k){int ll max(a[i]1,k*a[j]),rr min(maxx,(k1)*a[j]-1);if(llmaxx){continue;}int l b[ll],r c[rr];if(lr){continue;}sum (sumk*(pre[r][a[i]]-pre[l-1][a[i]])%mod)%mod;}ans (anscc*sum%mod)%mod;}}cout ans;return 0;}P12142 [蓝桥杯 2025 省 A] 黑客虽然此题有亿点坑但也真不至于绿。思路很显然设 \(n \times m2 n\)那么矩阵大小 \(a \times b n-2\)也就是说 \(n \bmod a 0,n \bmod b 0\)那么剩余的数能组成的方案就是\[\prod_{i 1}^{\max_{k 1}^n a_k} num_i \]\(num_i\) 指的是 \(i\) 出现的次数不能包含 \(a\) 和 \(b\) 这两个数那么显然这么做的时间复杂度是 \(O(nv)\)\(v\) 为值域显然过不去那么考虑到每次也最多改两个数的位置其实是可以通过简单推式子计算算出来的没必要每次都跑一遍先用一个变量 \(res\) 算出原本的 \(\prod_{i 1}^{\max_{k 1}^n a_k} num_i\)然后首先对于取了 \(a\) 这个数这个 \(a\) 不是数组那其实让 \(res\) 除以 \(num_a\) 就行然后让 \(num_a\) 减少 \(1\)然后对于 \(b\) 也是同理这题就搞定了带取模质数的除法用费马小定理就能搞定。本题坑点别忘了两个矩阵的行数和列数如果全部一样那就算重了。别忘了枚举约数只会枚举到 \(\sqrt{n-2}\)记得算行和列调换后的结果。算行和列调换时要注意 \(a b\) 的特殊情况。代码#includeusing namespace std;const int mod 1e97;const int N 5e55;int num[N];int jie[N];int a[N];int vis[N];inline int fast_pow(int a,int b){int ans 1;while(b){if(b1){ans 1ll*ans*a%mod;}a 1ll*a*a%mod;b1;}return ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,maxx 0;cin n;for(int i 1;in;i){cin a[i];maxx max(maxx,a[i]);num[a[i]];}jie[0] 1;for(int i 1;in;i){jie[i] 1ll*jie[i-1]*i%mod;}int res 1;for(int i 1;imaxx;i){if(num[i]){res 1ll*res*jie[num[i]]%mod;}}res fast_pow(res,mod-2);sort(a1,an1);int sum 0;for(int i 1;1ll*a[i]*a[i]n-2in;i){if((n-2)%a[i] 0!vis[a[i]]){vis[a[i]] 1;int j (n-2)/a[i];int ji 1ll*jie[n-2]*res%mod*num[a[i]]%mod;--num[a[i]];ji 1ll*ji*num[j]%mod;sum (sumji)%mod;if(a[i]!j){vis[j] 1;sum (sumji)%mod;}num[a[i]];}}cout sum;return 0;}P1680 奇怪的分组显然组合数学。先将 \(n\) 减去所有的 \(C_i\)那么问题就变成了将 \(n\) 个球放入 \(m\) 个盒子盒子不能为空的方案数显然可以用隔板法求。所谓隔板法就是解决盒子放球问题的经典模型我们先考虑盒子可以为空的情况所谓隔板就是在 \(n\) 个物品/球中放上隔板很显然要分 \(m\) 组就是 \(m-1\) 个隔板如图★★∣★★★∣★★★n 8,k 3那么方案数就是 \(C_{nk-1}^{k-1}\) 就是相当于从 \(nk-1\) 个隔板和球中选 \(k-1\) 个隔板的方案数盒子可以为空时就解决了那盒子不为空咋办很简单。我们先给每组分配一个物品只剩 \(n-1\) 个物品我们要在这 \(n-1\) 个物品中选择 \(k-1\) 个隔板所以是 \(C_{n-1}^{k-1}\)。这题显然是第二种于是预处理阶乘的逆元即可轻松解决。#includeusing namespace std;const int mod 1e97;const int N 1e65;int jie[N];inline int fast_pow(int a,int b){int ans 1;while(b){if(b1){ans 1ll*ans*a%mod;}a 1ll*a*a%mod;b1;}return ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin n m;for(int i 1;im;i){int x;cin x;n-x;}jie[0] 1;for(int i 1;in;i){jie[i] 1ll*jie[i-1]*i%mod;}--n;--m;cout 1ll*jie[n]*fast_pow(jie[n-m],mod-2)%mod*fast_pow(jie[m],mod-2)%mod;return 0;}P5148 大循环很显然 \(f(q)\) 是个很没用而且碍眼并且值又固定的东西那么预处理算出 \(f(q)\)然后问题转化成求长度为 \(k\) 值域为 \(1 \sim n\) 的序列中单调不降的序列个数那么仔细思考对于从 \(n\) 中任选 \(k\) 个重排一遍一定可以所以说就是 \(C_n^k\)答案为 \(C_n^k f(q)\)。代码#includeusing namespace std;const int mod 1e97;const int N 5e55;int a[N];int jie[N];inline int fast_pow(int a,int b){int ans 1;while(b){if(b1){ans 1ll*ans*a%mod;}a 1ll*a*a%mod;b1;}return ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,k,f 0;long long q;cin n m k q;q%mod;for(int i 0;im;i){cin a[i];f (f1ll*a[i]*fast_pow(q,i)%mod)%mod;}jie[0] 1;for(int i 1;in;i){jie[i] 1ll*jie[i-1]*i%mod;}cout 1ll*jie[n]*fast_pow(jie[n-k],mod-2)%mod*fast_pow(jie[k],mod-2)%mod*f%mod;return 0;}P5684 [CSP-J2019 江西] 非回文串首先容斥非回文串个数等于总个数减去回文串个数总个数显然是 \(n!\)那么回文串个数怎么算呢首先用 \(num\) 数组记录每个字母出现次数那么对于每个字母 \(x\) 先不考虑它本身的排列那么非回文串个数就是\[\frac{n}{2}!\prod_{i 1}^{26}\frac{1}{\frac{num_i}{2}!} \]加上每个字母本身的排列个数\[\frac{n}{2}!\prod_{i 1}^{26}\frac{num_i!}{\frac{num_i}{2}!} \]最终答案\[n!-\frac{n}{2}!\prod_{i 1}^{26}\frac{num_i!}{\frac{num_i}{2}!} \]记得特判本身不存在回文串的情况。#includeusing namespace std;const int mod 1e97;const int N 1e55;int num[N];int jie[N];char s[N];inline int fast_pow(int a,int b){int ans 1;while(b){if(b1){ans 1ll*ans*a%mod;}a 1ll*a*a%mod;b1;}return ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin n;cin s1;jie[0] 1;for(int i 1;in;i){jie[i] 1ll*jie[i-1]*i%mod;num[s[i]-a];}int cnt 0;for(int i 0;i26;i){if(num[i]1){cnt;}}if(cnt1){cout jie[n];return 0;}int res 1;for(int i 0;i26;i){if(!num[i]){continue;}res 1ll*res*jie[num[i]]%mod*fast_pow(jie[num[i]1],mod-2)%mod;}cout (jie[n]-1ll*jie[n1]*res%modmod)%mod;return 0;}