对 数组做前缀和 数组。
可发现 是由 数组循环累加上去的，可以先模 ，即 数组之和，然后 upper_bound 找即可。
#include<bits/stdc++.h>
#define LL long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mkp(x, y) make_pair(x, y)
#define Fcin \
ios :: sync_with_stdio(0);\
cin.tie(0); cout.tie(0)
using namespace std;
const LL N = 1e5 + 10;
LL n, x, A[N];
int main(){
Fcin;
cin >> n;
for (LL i = 1; i <= n; i ++){
cin >> A[i];
A[i] += A[i - 1];
}
cin >> x;
LL Ans = n * (x / A[n]);
x %= A[n];
cout << Ans + (upper_bound(A + 1, A + 1 + n, x) - A);
return 0;
}
DP.
状态 为合并至第 项时 的方案数。
#include<bits/stdc++.h>
#define LL long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mkp(x, y) make_pair(x, y)
#define Fcin \
ios :: sync_with_stdio(0);\
cin.tie(0); cout.tie(0)
using namespace std;
const LL N = 1e5 + 10;
LL n, A[N], DP[N][10];
int main(){
Fcin;
cin >> n;
for (LL i = 1; i <= n; i ++)
cin >> A[i];
DP[1][A[1]] = 1;
for (LL i = 2; i <= n; i ++){
for (LL j = 0; j <= 9; j ++){
DP[i][(A[i] + j) % 10] += DP[i - 1][j];
DP[i][(A[i] * j) % 10] += DP[i - 1][j];
}
for (LL j = 0; j <= 9; j ++)
DP[i][j] %= 998244353;
}
for (LL i = 0; i <= 9; i ++)
cout << DP[n][i] << "\n";
return 0;
}
可发现对于一条路径，有一点 ，路径起点在其左子树上，距离它 ，终点在它右子树上，距离它 。
枚举 ，，则可计算出起点、、终点的组合数，加入答案即可
起点有 种
有 种
终点有 种
注意起点终点可互换，答案乘以二。
#include<bits/stdc++.h>
#define LL long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define mkp(x, y) make_pair(x, y)
#define Fcin \
ios :: sync_with_stdio(0);\
cin.tie(0); cout.tie(0)
using namespace std;
const LL N = 1e5 + 10;
const LL MOD = 998244353;
LL n, D, Ans = 0;
LL Qpow(LL x, LL k){
LL res = 1, tmp = x;
while (k){
if (k & 1)
res = res * tmp % MOD;
tmp = tmp * tmp % MOD;
k >>= 1;
}
return res;
}
int main(){
cin >> n >> D;
for (LL i = 0; i <= D; i ++){
LL L = i, R = D - L;
if (max(L, R) >= n)
continue;
Ans = (Ans + 2 * Qpow(2, max(0LL, L - 1)) % MOD * Qpow(2, max(0LL, R - 1)) % MOD * (Qpow(2, max(0LL, n - max(L, R))) - 1) % MOD) % MOD;
}
cout << Ans;
return 0;
}
共 1 条回复
年轻人不错