经管之家App
让优质教育人人可得
立即打开
强壳钙固简易题，直接将区间求和转为前缀和，设 \(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_r+A_{l-1}B_{l-1} \] 显而易见 \(O(n)\) 枚举右端点 \(r\)，公式变为： \[\sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1} \] 如何迅速计算此公式？ 我们有： \[\sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{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}\) 显然需要额外维护两个前缀和乘积的前缀和。 代码：
全部版块
我的主页
收藏
#include
using namespace std;
const int mod = 1e9+7;
const int N = 5e5+5;
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;i<=n;++i)
{
cin >> a[i];
suma[i] = (suma[i-1]+a[i])%mod;
prea[i] = (prea[i-1]+suma[i])%mod;
}
for(int i = 1;i<=n;++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;i<=n;++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-B+mod)%mod-C+mod)%mod+D)%mod)%mod;
}
cout << sum;
return 0;
}
P8557 炼金术（Alchemy） 针对每种金属，它会被任意 \(1 \sim k\) 个熔炉炼制出来，因此方案数为 \(C_k^1+C_k^2+C_k^3+\dots+C_k^{k-1}+C_k^k = \sum_{i = 1}^k C_k^i\)，依据二项式定理，\((1+1)^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\)，使用快速幂计算即可。 代码：
#include
using namespace std;
const int mod = 998244353;
int fast_pow(int a,int b)
{
int ans = 1;
while(b)
{
if(b&1)
{
ans = 1ll*ans*a%mod;
}
a = 1ll*a*a%mod;
b>>=1;
}
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)-1+mod)%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} (i > k+1) \]
\[fg_i = 1 (i \le k+1) \]
问题迎刃而解。
代码：
#include
using namespace std;
const int mod = 5000011;
const int N = 1e5+5;
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; i <= n; ++i)
{
fn[i] = (fn[i-1] + fg[i-1]) % mod;
if (i > k+1)
{
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})\)。
代码：
#include
using namespace std;
const int N = 1e6+5;
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; i <= n; ++i)
{
cin >> a[i];
sum += a[i];
if (i > 1 && a[i] != a[i-1])
{
biao = 0;
}
}
if (biao)
{
cout << 0 << '\n';
}
for (int i = 1; i * i <= sum && i <= n; ++i)
{
if (sum % i == 0)
{
ans[++cnt] = i;
int s = sum / i;
if (s != i && s <= n)
{
ans[++cnt] = s;
}
}
}
sort(ans + 1, ans + cnt + 1);
for (int i = cnt; i; --i)
{
int num = sum / ans[i];
int summ = 0;
int flag = 1;
int res = 0;
for (int j = 1; j <= n; ++j)
{
if (summ + a[j] <= num)
{
summ += a[j];
}
else
{
flag = 0;
break;
}
if (summ == num)
{
++res;
summ = 0;
}
}
if (flag && res == 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_i>1\)），那么答案除了在仅有一个质因数时为 \(x\)，其余情况下皆为 \(1\)，不论奇偶性如何。为什么呢？其实很简单，即使质因数个数为奇数，也可以将其中一个拆分，使之变为偶数。若 \(x\) 没有因子是完全平方数，则需考虑其奇偶性，奇数时选取最小质因数（基于简单的贪心策略），偶数时则为 \(1\)，其原理较为直观，无需赘述。
代码：
#include
using 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*i<=n;++i)
{
if(n%i == 0)
{
if(!minn)
{
minn = i;
}
++num;
int cnt = 0;
while(n%i == 0)
{
++cnt;
n/=i;
}
if(cnt>1)
{
++shu;
}
}
}
if(n>1)
{
if(!minn)
{
minn = n;
}
++num;
}
if(!shu)
{
if(num&1)
{
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 \]
显然只有在 \(a>b>c\) 时才有贡献，因此可以考虑枚举 \(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(b+1,s \times c) \]
\[r = \min(\max_{i = 1}^n A_i,(s+1) \times c-1) \]
此外还需注意三点：
代码：
#include
using namespace std;
const int N = 5e3+5;
const long long mod = 1ll<<32;
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;i<=n;++i) { cin >> a[i]; maxx = max(maxx,a[i]); } sort(a+1,a+n+1); for(int i = 1;i<=n;++i) { for(int j = 1;j<=maxx;++j) { pre[i][j] = pre[i-1][j]+a[i]/j; } } for(int i = 1;i<=maxx;++i) { b[i] = lower_bound(a+1,a+n+1,i)-a; c[i] = upper_bound(a+1,a+n+1,i)-a-1; } long long ans = 0; for(int i = 1;i<=n;++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;k<=MAX;++k) { int ll = max(a[i]+1,k*a[j]),rr = min(maxx,(k+1)*a[j]-1); if(ll>maxx) { continue; } int l = b[ll],r = c[rr]; if(l>r) { continue; } sum = (sum+k*(pre[r][a[i]]-pre[l-1][a[i]])%mod)%mod; } ans = (ans+cc*sum%mod)%mod; } } cout << ans; return 0; }
P12142 [蓝桥杯 2025 省 A] 黑客
尽管这道题目有点棘手，但也不至于太过困难。解题思路十分明确，假设 \(n \times m + 2 = 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\) 同理。这样，题目就解决了，涉及模质数下的除法运算，可以利用费马小定理完成。
本题难点：
代码：
#include
using namespace std;
const int mod = 1e9+7;
const int N = 5e5+5;
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(b&1) {
ans = 1ll*ans*a%mod;
}
a = 1ll*a*a%mod;
b>>=1;
}
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;i<=n;++i) {
cin >> a[i];
maxx = max(maxx,a[i]);
++num[a[i]];
}
jie[0] = 1;
for(int i = 1;i<=n;++i) {
jie[i] = 1ll*jie[i-1]*i%mod;
}
int res = 1;
for(int i = 1;i<=maxx;++i) {
if(num[i]) {
res = 1ll*res*jie[num[i]]%mod;
}
}
res = fast_pow(res,mod-2);
sort(a+1,a+n+1);
int sum = 0;
for(int i = 1;1ll*a[i]*a[i]<=n-2&&i<=n;++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 = (sum+ji)%mod; if(a[i]!=j) { vis[j] = 1; sum = (sum+ji)%mod; } ++num[a[i]]; } } cout << sum; return 0; }
P1680 特殊的分组 显然涉及组合数学。 首先将 \(n\) 减少所有 \(C_i\)，这样问题转化为将 \(n\) 个球放入 \(m\) 个盒子里（每个盒子不可为空）的方法数，显然可以通过插板法来计算。 所谓的插板法，是处理盒子里放球问题的经典方法。假设盒子可以为空，即在 \(n\) 个物品/球之间插入隔板，显然分成 \(m\) 组就需要 \(m-1\) 个隔板，例如： ★★∣★★★∣★★★ n = 8,k = 3 因此，方案数为 \(C_{n+k-1}^{k-1}\)，即从 \(n+k-1\) 个隔板和球中选取 \(k-1\) 个隔板的方式数。当盒子不允许为空时，解决方案变得简单。 我们可以先给每组分配一个物品，剩下 \(n-1\) 个物品，在这些物品中选择 \(k-1\) 个隔板，所以方案数变为 \(C_{n-1}^{k-1}\)。 本题显然属于后者，通过预处理阶乘的逆元即可轻松解决。 #include using namespace std; const int mod = 1e9+7; const int N = 1e6+5; int jie[N]; inline int fast_pow(int a,int b) { int ans = 1; while(b) { if(b&1) { ans = 1ll*ans*a%mod; } a = 1ll*a*a%mod; b>>=1; } 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;i<=m;++i) { int x; cin >> x; n-=x; } jie[0] = 1; for(int i = 1;i<=n;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)\)。 代码： #include using namespace std; const int mod = 1e9+7; const int N = 5e5+5; int a[N]; int jie[N]; inline int fast_pow(int a,int b) { int ans = 1; while(b) { if(b&1) { ans = 1ll*ans*a%mod; } a = 1ll*a*a%mod; b>>=1; } 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;i<=m;++i) { cin >> a[i]; f = (f+1ll*a[i]*fast_pow(q,i)%mod)%mod; } jie[0] = 1; for(int i = 1;i<=n;++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}!} \]
请特别注意处理不存在回文串的情况。
#include
using namespace std;
const int mod = 1e9+7;
const int N = 1e5+5;
int num[N];
int jie[N];
char s[N];
inline int fast_pow(int a,int b)
{
int ans = 1;
while(b)
{
if(b&1)
{
ans = 1ll*ans*a%mod;
}
a = 1ll*a*a%mod;
b>>=1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
cin >> s+1;
jie[0] = 1;
for(int i = 1;i<=n;++i)
{
jie[i] = 1ll*jie[i-1]*i%mod;
++num[s[i]-'a'];
}
int cnt = 0;
for(int i = 0;i<26;i++)
{
if(num[i]&1)
{
++cnt;
}
}
if(cnt>1)
{
cout << jie[n];
return 0;
}
int res = 1;
for(int i = 0;i<26;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[n>>1]*res%mod+mod)%mod;
return 0;
}
扫码加好友，拉您进群
