ARC067
C - Factors of Factorial
这个直接套公式就是，先求出来每个质因数的指数幂，然后约数个数就是
\((1 + e_{1})(1 + e_{2})(1 + e_{3})\cdots(1 + e_k)\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N;
int prime[1005],tot;
bool nonprime[1005];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int f(int n,int p) {
if(n < p) return 0;
return f(n / p ,p) + n / p;
}
void Solve() {
read(N);
for(int i = 2 ; i <= N ; ++i) {
if(!nonprime[i]) {prime[++tot] = i;}
for(int j = 1 ; j <= tot ; ++j) {
if(i * prime[j] > N) break;
nonprime[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
int ans = 1;
for(int i = 1 ; i <= tot ; ++i) {
ans = mul(ans,f(N,prime[i]) + 1);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
D - Walk and Teleport
走比较花费少就走，否则就传送
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int64 X[MAXN],A,B;
void Solve() {
read(N);read(A);read(B);
for(int i = 1 ; i <= N ; ++i) read(X[i]);
int64 ans = 0;
for(int i = 2 ; i <= N ; ++i) {
ans += min(B,(X[i] - X[i - 1]) * A);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
E - Grouping
我直接做背包看起来是\(N^{3}\)
然而\(N + \frac{N}{2} + \frac{N}{3}...\)是\(Nlog N\)就过了
若从i个人转移到\(i + kt\)的时候，就是多出k组人数为t，方案数是
\(\binom{kt}{N - i}\frac{(kt)!}{(t!)^k} \frac{1}{k!}\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,A,B,C,D;
int dp[MAXN][MAXN],c[MAXN][MAXN],fac[MAXN],invfac[MAXN],g[MAXN];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void update(int &x,int y) {
x = inc(x,y);
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
void Solve() {
read(N);read(A);read(B);read(C);read(D);
c[0][0] = 1;
for(int i = 1 ; i <= N ; ++i) {
c[i][0] = 1;
for(int j = 1 ; j <= i ; ++j) {
c[i][j] = inc(c[i - 1][j],c[i - 1][j - 1]);
}
}
fac[0] = 1;
for(int i = 1 ; i <= N ; ++i) fac[i] = mul(fac[i - 1],i);
invfac[N] = fpow(fac[N],MOD - 2);
for(int i = N - 1 ; i >= 0 ; --i) {
invfac[i] = mul(invfac[i + 1],i + 1);
}
dp[0][0] = 1;
for(int i = 1 ; i <= B - A + 1; ++i) {
int t = i + A - 1;
for(int j = 0 ; j <= N ; ++j) {
dp[i][j] = dp[i - 1][j];
for(int k = C ; k <= D ; ++k) {
if(k * t > j) break;
int tmp = mul(dp[i - 1][j - k * t],c[N - j + k * t][k * t]);
tmp = mul(fac[k * t],tmp);
tmp = mul(tmp,fpow(invfac[t],k));
tmp = mul(tmp,invfac[k]);
update(dp[i][j],tmp);
}
}
}
out(dp[B - A + 1][N]);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
F - Yakiniku Restaurants
我对于第i种票每次选出一个最大的\(B[x][i]\)，\(l <= x <= r\)
这是一个矩阵加，可以直接差分套一下
然后分到两边继续算，可以用RMQ找区间最大值的位置
复杂度是\(N\log NM + N^{2}\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 5005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
int64 sum[MAXN][MAXN],A[MAXN],B[MAXN][205],st[MAXN][15],len[MAXN];
int maxpos(int l,int x,int y) {
return B[x][l] > B[y][l] ? x : y;
}
int Query(int x,int l,int r) {
int t = len[r - l + 1];
return maxpos(x,st[l][t],st[r - (1 << t) + 1][t]);
}
void dfs(int x,int l,int r) {
if(l > r) return;
int p = Query(x,l,r);
sum[l][p] += B[p][x];
sum[l][r + 1] -= B[p][x];
sum[p + 1][p] -= B[p][x];
sum[p + 1][r + 1] += B[p][x];
dfs(x,l,p - 1);dfs(x,p + 1,r);
}
void Solve() {
read(N);read(M);
for(int i = 1 ; i < N ; ++i) {
read(A[i]);
A[i] += A[i - 1];
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
read(B[i][j]);
}
}
for(int i = 2 ; i <= N ; ++i) len[i] = len[i / 2] + 1;
for(int j = 1 ; j <= M ; ++j) {
for(int i = 1 ; i <= N ; ++i) st[i][0] = i;
for(int k = 1 ; k <= 13 ; ++k) {
for(int i = 1 ; i <= N ; ++i) {
if(i + (1 << k) - 1 > N) break;
st[i][k] = maxpos(j,st[i][k - 1],st[i + (1 << k - 1)][k - 1]);
}
}
dfs(j,1,N);
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
sum[i][j] += sum[i][j - 1];
}
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
sum[i][j] += sum[i - 1][j];
}
}
int64 ans = 0;
for(int i = 1 ; i <= N ; ++i) {
for(int j = i ; j <= N ; ++j) {
ans = max(sum[i][j] - (A[j - 1] - A[i - 1]),ans);
}
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}