A. 烷基计数
/(f[i]/)表示由/(i/)个碳原子构成的烷基数量
/(g[i][j]/)表示由/(i/)个碳原子构成的只有两棵子树，其中较小的一棵大小为/(j/)的烷基数量
求/(f[i]/)，先考虑只有两棵子树的情况，如果两个子树大小不一样那么有/(f[j] * f[i – 1 – j]/)种方案，如果两棵子树大小相同，那就不能直接乘起来，需要用可以重复选择的组合数，是/(H_{f[j]}^2/)
然后我们对/(g/)数组进行后缀求和，此时它表示的是较小的一棵子树大于等于/(j/)的烷基数量
这样方便我们对/(f[i]/)求解
考虑三棵子树的请况，枚举最小子树/(j/)，通过/(g[i – j][j + 1]/)可以求出部分答案
剩下的就是三棵子树都相等，或者最小的子树/(j/)和次小的子树相等
两个方案分别是/(H_{f[j]}^3/)和/(H_{f[j]}^2 * f[i – 1 – j – j]/)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 5005;
typedef long long ll;
int n, mod, inv[maxn];
ll qpow(ll x,ll y){
ll ans = 1;
for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;
return ans;
}
ll c(int n,int m){
ll ans = 1;
for(int i = n; i >= n - m + 1; --i)ans = ans * i % mod;
for(int i = 1; i <= m; ++i)ans = ans * inv[i] % mod;
return ans;
}
ll H(int n,int m){return c(n + m - 1,m);}
ll f[maxn],g[maxn][maxn];
int main(){
scanf("%d%d",&n,&mod);
for(int i = 1; i <= 100; ++i)inv[i] = qpow(i, mod - 2);
f[0] = f[1] = f[2] = 1;
for(int i = 3; i <= n; ++i){
f[i] = f[i - 1];
for(int j = (i - 1) / 2; j; --j){
if(j + j == i - 1)g[i][j] = (g[i][j] + H(f[j], 2)) % mod;
else g[i][j] = (g[i][j] + f[j] * f[i - j - 1] % mod) % mod;
f[i] = (f[i] + g[i][j]) % mod;
}
for(int j = (i - 1) / 2; j; --j)g[i][j] = (g[i][j] + g[i][j + 1]) % mod;
for(int j = (i - 1) / 3; j; --j){
f[i] = (f[i] + f[j] * g[i - j][j + 1] % mod) % mod;
if(j + j + j == i - 1)f[i] = (f[i] + H(f[j], 3)) % mod;
else f[i] = (f[i] + H(f[j], 2) * f[i - 1 - j - j]) % mod;
}
}
printf("%lld/n",f[n]);
return 0;
}
B. mine
假/(DP/)，真分讨
不过我的状态太麻烦了，
题解状态定义的很好，转移比较方便，启示：合并同类状态
定义状态 /(dp/) 就行了,/(dp_{i,0/1/2}/) 分别表示考虑到 /(i/) 要求后面再有 /(0/) 个雷的方案数,要求 /(i/) 后面再有 /(1/) 个雷的方案数,以及 /(i/) 是雷的方案数
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 55;
const int mod = 1e9 + 7;
char s[maxn];
int n;
ll f[maxn][9];
int main(){
scanf("%s",s + 1);
n = strlen(s + 1);
if(n == 1){
printf("%d/n",s[1] == '?' ? 4 : 1);
return 0;
}
if(s[1] != '?'){
if(s[1] == '0')f[1][0] = f[1][3] = 1;
if(s[1] == '1')f[1][5] = 1;
if(s[1] == '*')f[1][2] = f[1][6] = f[1][8] = 1;
}else {
f[1][0] = f[1][3] = f[1][5] = f[1][2] = f[1][6] = f[1][8] = 1;
}
for(int i = 2; i < n; ++i){
if(s[i] == '0'){
f[i][0] = f[i][3] = (f[i - 1][0] + f[i - 1][4]) % mod;
}
if(s[i] == '1'){
f[i][1] = f[i - 1][6];
f[i][4] = f[i - 1][6];
f[i][5] = (f[i - 1][1] + f[i - 1][3]) % mod;
}
if(s[i] == '2'){
f[i][7] = f[i - 1][8];
}
if(s[i] == '*'){
f[i][2] = f[i][6] = f[i][8] = (f[i - 1][5] + f[i - 1][7] + f[i - 1][2]) % mod;
}
if(s[i] == '?'){
f[i][0] = f[i][3] = (f[i - 1][0] + f[i - 1][4]) % mod;
f[i][1] = f[i - 1][6];
f[i][4] = f[i - 1][6];
f[i][5] = (f[i - 1][1] + f[i - 1][3]) % mod;
f[i][7] = f[i - 1][8];
f[i][2] = f[i][6] = f[i][8] = (f[i - 1][5] + f[i - 1][7] + f[i - 1][2]) % mod;
}
}
ll ans = 0;
if(s[n] != '?'){
if(s[n] == '0')ans = f[n - 1][0] + f[n - 1][4];
if(s[n] == '1')ans = f[n - 1][6];
if(s[n] == '*')ans = f[n - 1][2] + f[n - 1][5] + f[n - 1][7];
}else {
ans = f[n - 1][0] + f[n - 1][4] + f[n - 1][6] + f[n - 1][2] + f[n - 1][5] + f[n - 1][7];
}
// for(int i = 1; i <= n; ++i){
// for(int j = 0; j < 9; ++j)printf("%d ",f[i][j]);
// puts("");
// }
printf("%lld/n",ans % mod);
return 0;
}
C. 小凯的疑惑
通过打表不难发现，答案为/((x – 1) (y – 1) / 2/)
考虑到若 /((x,y)/neq 1/) 那么一定输出 /(-1/),所以我们只需要考虑 /((x,y)=1/) 的情况.
因为有：若 /(a_i(1/le i/le n)/) 构成模 /(n/) 的完系,/(k.m/in Z/)，/((m,n)=1/)，则 /(k+ma_i(1/le i/le n)/) 也构成模 /(n/) 的完系.我们可以考虑模 /(b/) 为 /(1/) 到 /(b-1/) 的每个值最小什么时候出现,那么显然此时我们不选 /(b/),然后又由于上述性质,我们可以直接求出余数为每个值的最小值.
由此可知,答案为
/[/sum_{i=1}^{y-1}/lfloor/frac{ix}{y}/rfloor
/]
简单化简即可得到答案.
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);}
typedef long long ll;
int main(){
int x,y; scanf("%d%d",&x,&y);
if(gcd(x,y) != 1)printf("-1/n");
else{
if(x > y)swap(x,y);
printf("%lld",1ll * (x - 1) * (y - 1) /2);
}
return 0;
}
D. 排序
二分答案，把大于等于当前值的设成/(1/)，其余设成/(0/)，线段树维护可以做到/(mlognlogn/)
据说是常规套路》
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
return x;
}
const int maxn = 1e5 +55;
int n, m, a[maxn], now[maxn], p;
struct upd{int op,l,r;}o[maxn];
struct tree{
struct node{
int tag, size;
}t[maxn << 2 | 1];
void push_up(int x){
t[x].size = t[x << 1].size + t[x << 1 | 1].size;
}
void built(int x, int l, int r){
t[x].size = t[x].tag = 0;
if(l == r){t[x].size = now[l];return;}
int mid = (l + r) >> 1;
built(x << 1, l, mid);
built(x << 1 | 1, mid + 1, r);
push_up(x);
}
void push_down(int x, int l, int r){
int ls = x << 1, rs = x << 1 | 1, mid = (l + r) >> 1;
if(t[x].tag == 1){
t[ls].size = mid - l + 1;
t[rs].size = r - mid;
t[ls].tag = t[rs].tag = 1;
}else{
t[ls].size = t[rs].size = 0;
t[ls].tag = t[rs].tag = -1;
}
t[x].tag = 0;
}
void modify(int x, int l, int r, int L, int R, int upd){
if(L > R)return;
// if(x == 1)printf("modify : %d %d %d/n",L, R, upd);
if(L <= l && r <= R){
if(upd){
t[x].size = (r - l + 1);
t[x].tag = 1;
}else{
t[x].size = 0; t[x].tag = -1;
}
return;
}
if(t[x].tag)push_down(x, l, r);
int mid = (l + r) >> 1;
if(L <= mid)modify(x << 1, l, mid, L, R, upd);
if(R > mid)modify(x << 1 | 1, mid + 1, r, L, R, upd);
push_up(x);
}
int query(int x, int l, int r, int L, int R){
if(L <= l && r <= R)return t[x].size;
if(t[x].tag)push_down(x, l, r);
int mid = (l + r) >> 1, ans = 0;
if(L <= mid)ans += query(x << 1, l, mid, L, R);
if(R > mid)ans += query(x << 1 | 1, mid + 1, r, L, R);
return ans;
}
}T;
bool check(int mid){
// printf("/ncheck : %d /n", mid);
for(int i = 1; i <= n; ++i)now[i] = a[i] >= mid ? 1 : 0;
T.built(1, 1, n);
for(int i = 1; i <= m; ++i){
int cnt = T.query(1, 1, n, o[i].l, o[i].r);
int u1 = 1, u0 = 0;
if(o[i].op) swap(u1, u0);else cnt = o[i].r - o[i].l + 1 - cnt;
// for(int j = 1; j <= n; ++j)printf("%d ",T.query(1, 1, n, j, j));puts("");
T.modify(1, 1, n, o[i].l, o[i].l + cnt - 1, u0);
// for(int j = 1; j <= n; ++j)printf("%d ",T.query(1, 1, n, j, j));puts("");
T.modify(1, 1, n, o[i].l + cnt, o[i].r, u1);
// for(int j = 1; j <= n; ++j)printf("%d ",T.query(1, 1, n, j, j));puts("");
}
return T.query(1, 1, n, p, p);
}
int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++i)a[i] = read();
for(int i = 1; i <= m; ++i)o[i].op = read(), o[i].l = read(), o[i].r = read();
p = read();
int l = maxn, r = -maxn;
for(int i = 1; i <= n; ++i)l = min(l, a[i]), r = max(r, a[i]);
int ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid))ans = mid, l = mid + 1;
else r = mid - 1;
}
printf("%d/n",ans);
return 0;
}
原创文章，作者：306829225，如若转载，请注明出处：https://blog.ytso.com/277559.html