目錄

• day5
  • 5H div2 Nested Tree (樹形dp)
  • 5F div2 Kropki (狀壓dp)
  • 5J div1 Special Judge (計算幾何)
  • 5I div1 Sorting (線段樹)
  • 5D div1 Doppelblock (搜索)
  • 5C div1 Division (主席樹)
  • 5E div1 Fast Kronecker Transform (NTTorFFT)
• day7
  • 7G div1&2 搶紅包機器人 (拓撲序)
  • 7A div1 迷宮 (樹 規律)
  • 7E div2 線性探查法 (暴力)
  • 7C div1 斐波那契數列 (打表找規律)
  • 7F div2 逆序對！ (規律)
  • 7J div1&2 強壯的排列
  • 7H div2 同構 整數劃分
  • 7H div1 同構 整數劃分
• day8
  • 8G div1&2 穗乃果的考試 (計數)
  • 8D div2 吉良吉影的奇妙計劃 (dp)
  • 8A div1 Aqours (性質 dp)
  • 8B div1 玖凜兩開花 (匈牙利+枚舉or二分)
  • 8E div2 Souls-like Game (矩陣乘法 優化)
  • 8E div1 Souls-like Game (線段樹+矩陣乘法)
  • 8I div1 岸邊露伴的人生經驗 (FWT)

本來是8天代碼放一起的，但是太麻煩了，還是分成了2個博客放。

day5

5H div2 Nested Tree (樹形dp)

//H #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 2e6 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; LL n, m; std::vector<int> mp[MXN]; LL siz[MXN]; LL ans; void dfs(int u,int ba) {siz[u] = 1;for(auto v: mp[u]) {if(v == ba) continue;dfs(v, u);siz[u] += siz[v];ans += siz[v] *(n*m-siz[v])%mod;ans = (ans%mod + mod)%mod;} } int main(){scanf("%lld%lld", &n, &m);for(int i = 1, a, b; i < n; ++i) {scanf("%d%d", &a, &b);for(int j = 0; j < m; ++j) {mp[a+j*n].push_back(b+j*n);mp[b+j*n].push_back(a+j*n);}}for(int i = 1, a, b, u, v; i < m; ++i) {scanf("%d%d%d%d", &a, &b, &u, &v); --a, --b;mp[a*n+u].push_back(b*n+v);mp[b*n+v].push_back(a*n+u);}dfs(1, 1);printf("%lld\n", ans);return 0; }

5F div2 Kropki (狀壓dp)

//F #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 2e6 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, m; LL dp[1<<16][16]; char s[MXN]; int get_num(int x) {bitset<40> sb(x);return sb.count(); } int main(){scanf("%d%s", &n, s+1);memset(dp, 0, sizeof(dp));for(int i = 0; i < n; ++i) {dp[1<<i][i] = 1;}int sta = 1<<n;for(int t = 1; t < sta; ++t) {for(int i = 0; i < n; ++i) {if(!(t & (1 << i))) continue;for(int j = 0; j < n; ++j) {if(i == j) continue;if(!(t&(1<<j))) continue;int old = t^(1<<i);if(dp[old][j] == -1) continue;int h = get_num(old);if(h == 0) continue;if(s[h] == '1' && ((j+1)*2 == i+1||(i+1)*2==j+1)) {//if(dp[t][i] == -1) dp[t][i] = 0;dp[t][i] += dp[old][j];}else if(s[h] == '0' && (j+1)*2!=i+1&&(i+1)*2!=j+1){//if(dp[t][i] == -1) dp[t][i] = 0;dp[t][i] += dp[old][j];}if(dp[t][i] >= mod) dp[t][i] %= mod;}}}LL ans = 0;for(int i = 0; i < n; ++i) {if(dp[sta-1][i] == -1) continue;ans = (ans + dp[sta-1][i]) % mod;}printf("%lld\n", ans);return 0; }

5J div1 Special Judge (計算幾何)

//J #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) #define db LL using namespace std; typedef long long LL; typedef pair<int, LL> pii; #define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y)) #define crossOp(p1,p2,p3) sign(cross(p1,p2,p3)) const int MXN = 1e5 + 6; const int INF = 0x3f3f3f3f; const double eps = 1e-9; int n, m; struct P {db x, y;P(){};P(db _x, db _y):x(_x),y(_y){}P operator+(P p){return {x+p.x,y+p.y};}P operator-(P p){return {x-p.x,y-p.y};}db dot(P p) {return x*p.x+y*p.y;}db det(P p) {return x*p.y-y*p.x;} }; inline int sign(db a) {return a < -eps?-1:a>eps;} inline int cmp(db a, db b) {return sign(a-b);}bool intersect(db l1, db r1, db l2, db r2) {if(l1 > r1) swap(l1, r1);if(l2 > r2) swap(l2, r2);return !(cmp(r1,l2)==-1||cmp(r2,l1)==-1); } bool isSS(P p1, P p2, P q1, P q2) {//判斷線段相交return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<=0&&crossOp(q1,q2,p1)*crossOp(q1,q2,p2)<=0; } bool isSS_strict(P p1, P p2, P q1, P q2) {//嚴格相交return crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<0&&crossOp(q1,q2,p1)*crossOp(q1,q2,p2) < 0; } bool isMiddle(db a, db m, db b) {return sign(a-m)==0||sign(b-m)==0||(a<m!=b<m); } bool isMiddle(P a, P m, P b) {return isMiddle(a.x,m.x,b.x)&&isMiddle(a.y,m.y,b.y); } bool onSeg(P p1, P p2, P q) {return crossOp(p1,p2,q) == 0 && isMiddle(p1,q,p2); } bool ojbk(P p1, P p2, P q1, P q2) {P p = p2 - p1;P q = q2 - q1;if(q.det(p) == 0) return 1;return 0; } double rad(P p1, P p2) {return atan2(p1.det(p2),p1.dot(p2)); } bool xielv(P p1, P p2, P q1, P q2) {P p = p2 - p1;P q = q2 - q1;if(q.det(p) == 0 && cmp(rad(p, q), 0) == 0) return 1;return 0; } struct lp {int a, b; }cw[MXN]; LL x[MXN], y[MXN]; int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i) {scanf("%d%d", &cw[i].a, &cw[i].b);}for(int i = 1; i <= n; ++i) {scanf("%lld%lld", &x[i], &y[i]);}int cnt = 0;for(int i = 1; i <= m; ++i) {for(int j = i + 1; j <= m; ++j) {P p1 = {x[cw[i].a],y[cw[i].a]};P p2 = {x[cw[i].b],y[cw[i].b]};P q1 = {x[cw[j].a],y[cw[j].a]};P q2 = {x[cw[j].b],y[cw[j].b]};//printf("%d %d %d %d\n", cw[i].a, cw[i].b, cw[j].a, cw[j].b);//printf("%lld %lld\n", q2.x,q2.y);if(isSS(p1,p2,q1,q2)) {if(cw[i].a==cw[j].a || cw[i].a==cw[j].b||cw[i].b==cw[j].a||cw[i].b==cw[j].b) {//printf("%lld %lld %lld %lld %lld %lld %lld %lld\n", p1.x,p1.y,p2.x,p2.y,q1.x,q1.y,q2.x,q2.y);if(cw[i].a==cw[j].a&&xielv(p1,p2,q1,q2)) cnt++;if(cw[i].a==cw[j].b&&xielv(p1,p2,q2,q1)) cnt++;if(cw[i].b==cw[j].a&&xielv(p2,p1,q1,q2)) cnt++;if(cw[i].b==cw[j].b&&xielv(p2,p1,q2,q1)) cnt++;}else cnt++;}}}printf("%d\n", cnt);return 0; }

5I div1 Sorting (線段樹)

//I #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 1e6 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, q, x; int ar[MXN]; int sum1[MXN<<2], sum2[MXN<<2], flag[MXN<<2]; LL num1[MXN], num2[MXN]; void push_up(int rt) {sum1[rt] = sum1[rt<<1] + sum1[rt<<1|1];sum2[rt] = sum2[rt<<1] + sum2[rt<<1|1]; } void build(int l,int r,int rt) {flag[rt] = -1;if(l == r) {if(ar[l] > x) sum2[rt] = 1;else sum1[rt] = 1;return;}int mid = (l + r) >> 1;build(l, mid,rt<<1); build(mid+1, r,rt<<1|1);push_up(rt); } void push_down(int l,int mid,int r,int rt) {if(flag[rt] == -1) return ;flag[rt<<1] = flag[rt];flag[rt<<1|1] = flag[rt];if(flag[rt] == 0) {sum1[rt<<1] = mid-l+1;sum1[rt<<1|1] = r-mid;sum2[rt<<1] = 0;sum2[rt<<1|1] = 0;}else {sum1[rt<<1] = 0;sum1[rt<<1|1] = 0;sum2[rt<<1] = mid-l+1;sum2[rt<<1|1] = r-mid;}flag[rt] = -1; } void update(int L, int R,int v,int l,int r,int rt) {if(L > R) return ;if(L <= l && r <= R) {if(v == 0) sum1[rt] = r - l + 1,sum2[rt] = 0;else sum2[rt] = r - l + 1,sum1[rt] = 0;flag[rt] = v;return;}int mid = (l + r) >> 1;push_down(l, mid, r, rt);if(L > mid) update(L, R, v,mid+1,r,rt<<1|1);else if(R <= mid) update(L,R,v,l,mid,rt<<1);else {update(L,mid,v,l,mid,rt<<1), update(mid+1,R,v,mid+1,r,rt<<1|1);}push_up(rt); } int query1(int L,int R,int l,int r,int rt,int id) {if(L > R) return 0;if(L <= l && r <= R) {if(id == 0)return sum1[rt];return sum2[rt];}int mid = (l + r) >> 1;push_down(l, mid, r, rt);if(L > mid) return query1(L, R, mid+1,r,rt<<1|1,id);else if(R <= mid) return query1(L,R,l,mid,rt<<1,id);else {return query1(L,mid,l,mid,rt<<1,id) + query1(mid+1,R,mid+1,r,rt<<1|1,id);} } int main(){scanf("%d%d%d", &n, &q, &x);for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);int cnt1 = 0, cnt2 = 0;for(int i = 1; i <= n; ++i) {if(ar[i] <= x) ++ cnt1, num1[cnt1] = num1[cnt1-1]+ar[i];else ++ cnt2, num2[cnt2] = num2[cnt2-1]+ar[i];}build(1, n, 1);int p, l, r;while(q --) {scanf("%d%d%d", &p, &l, &r);if(p == 1) {int p0 = query1(1,l-1,1,n,1,0), p1 = query1(1,r,1,n,1,0);int q0 = query1(1,l-1,1,n,1,1), q1 = query1(1,r,1,n,1,1);printf("%lld\n", num1[p1] - num1[p0] + num2[q1] - num2[q0]);}else if(p == 2) {int sb1 = query1(l,r,1,n,1,0);if(sb1) update(l,l+sb1-1,0,1,n,1);update(l+sb1,r,1,1,n,1);}else {int sb2 = query1(l,r,1,n,1,1);if(sb2) update(l,l+sb2-1,1,1,n,1);update(l+sb2,r,0,1,n,1);}}return 0; }

5D div1 Doppelblock (搜索)

//D楊栩 #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii; const int MXN = 2e6 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n; int vis[15][15]; int visr[15][15]; int visc[15][15]; int needr[15]; int needc[15]; int nowrx[15],nowcx[15];// di i 行 第一個x的縱坐標 豎 橫坐標 int haverx[15],havecx[15]; int nowc[15],nowr[15]; int totc[15],totr[15]; int flag = 0; int sum; bool check() {for(int i=1; i<=n; i++) {if(havecx[i]!=2 || haverx[i]!=2) {return 0;}}return 1; } void dfs(int x,int y) {//cout<<"now:"<<x<<","<<y<<",,"<<flag<<endl;if(haverx[x]==0 && sum-totr[x]<needr[x]) return;if(havecx[y]==0 && sum-totc[y]<needc[y]) return;if(flag ) return ;if(x==n+1) {if(check())flag = 1;//cout<<"haha:"<<flag<<endl;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(vis[i][j]!=-1) {printf("%d",vis[i][j]);} else {printf("X");}}puts("");}return ;} // for(int i=1; i<=n; i++) { // for(int j=1; j<=n; j++) { // if(vis[i][j]!=-1) { // printf("%d",vis[i][j]); // } else { // printf("X"); // } // } // puts(""); // }// 判斷是否可放xif(haverx[x]==0 &&havecx[y]==0) {nowrx[x]=y;nowcx[y]=x;havecx[y]++;haverx[x]++;vis[x][y]=-1;if(y+1>n) {if(haverx[x]==2)dfs(x+1,1);} else {dfs(x,y+1);}vis[x][y]=0;nowrx[x]=0;nowcx[y]=0;havecx[y]--;haverx[x]--;}// 橫有了一個x 豎沒有xelse if(haverx[x]==1 && havecx[y]==0) {int cnt = nowr[x];//getnum(nowrx[x],y,x,1);//cout<<"cnt:"<<cnt<<endl;// 第 i 行 兩個x之間的屬的和滿足riif(cnt==needr[x]) {havecx[y]++;haverx[x]++;nowcx[y]=x;vis[x][y]=-1;if(y+1>n) {if(haverx[x]==2)dfs(x+1,1);} else {dfs(x,y+1);}vis[x][y]=0;havecx[y]--;haverx[x]--;nowcx[y]=0;}}// 豎有了一個x 橫沒有xelse if(haverx[x]==0 && havecx[y]==1) {int cnt = nowc[y];//getnum(nowcx[y],x,y,0);// 第 i 行 兩個x之間的屬的和滿足riif(cnt==needc[y]) {havecx[y]++;haverx[x]++;nowrx[x]=y;vis[x][y]=-1;if(y+1>n) {if(haverx[x]==2)dfs(x+1,1);} else {dfs(x,y+1);}vis[x][y]=0;havecx[y]--;haverx[x]--;nowrx[x]=0;}}// 橫豎都有一個else {int cnt1 = nowr[x];//getnum(nowrx[x],y,x,1);int cnt2 = nowc[y];//getnum(nowcx[y],x,y,0);if(cnt1 == needr[x] && cnt2 == needc[y]) {havecx[y]++;haverx[x]++;vis[x][y]=-1;if(y+1>n) {if(haverx[x]==2)dfs(x+1,1);} else {dfs(x,y+1);}vis[x][y]=0;havecx[y]--;haverx[x]--;}}for(int i=1; i<=n-2; i++) {int cnt1 = 0;if(haverx[x]==1) {cnt1 =nowr[x];//getnum(nowrx[x],y,x,1);if(cnt1+i>needr[x]) continue;//cout<<"cnt1+i:"<<cnt1+i<<"vs"<<needr[x]<<endl;}int cnt2 = 0;if(havecx[y]==1) {cnt2 = nowc[y];//getnum(nowcx[y],x,y,0);if(cnt2+i>needc[y]) continue;}if(visc[y][i]==0 && visr[x][i]==0 ) {visc[y][i]=1;visr[x][i]=1;vis[x][y]=i;totc[y]+=i;totr[x]+=i;if(haverx[x]==1) {nowr[x]+=i;}if(havecx[y]==1) {nowc[y]+=i;}if(y+1>n) {if(haverx[x]==2)dfs(x+1,1);} else {dfs(x,y+1);}if(haverx[x]==1) {nowr[x]-=i;}if(havecx[y]==1) {nowc[y]-=i;}totc[y]-=i;totr[x]-=i;visc[y][i]=0;visr[x][i]=0;vis[x][y]=0;}} } void init() {flag = 0;memset(vis,0,sizeof vis);memset(visr,0,sizeof visr);memset(visc,0,sizeof visc);memset(needr,0,sizeof needr);memset(needc,0,sizeof needc);memset(nowrx,0,sizeof nowrx);memset(nowcx,0,sizeof nowcx);memset(haverx,0,sizeof haverx);memset(havecx,0,sizeof havecx);memset(nowc,0,sizeof nowc);memset(nowr,0,sizeof nowr);memset(totc,0,sizeof totc);memset(totr,0,sizeof totr);sum=0;for(int i=1; i<=n-2; i++) {sum+=i;} // cout<<sum<<endl; } int main() {int T;scanf("%d",&T);while(T--) {scanf("%d",&n);init();for(int i=1; i<=n; i++) {scanf("%d",&needr[i]);}for(int j=1; j<=n; j++) {scanf("%d",&needc[j]);}dfs(1,1);if(T)puts("");} }

5C div1 Division (主席樹)

//C 題解：https://blog.csdn.net/qq_39599067/article/details/86650060 #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 1e6 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, q; int ar[MXN], num[MXN]; LL sum[MXN]; struct QUERY {int l, r, k;LL ans; }cw[MXN]; struct lp {int l, r, cnt;LL sum; }node[MXN*16]; int inde, Root[MXN]; void z_update(int old, int &cur, int val, LL L, LL R) {cur = ++ inde;node[cur] = node[old];if(L == R) {node[cur].sum += val - val/2;++ node[cur].cnt;return;}LL mid = (L + R) / 2;if(val <= mid) z_update(node[old].l, node[cur].l, val, L, mid);else z_update(node[old].r, node[cur].r, val, mid+1, R);node[cur].sum = node[node[cur].l].sum + node[node[cur].r].sum;node[cur].cnt = node[node[cur].l].cnt + node[node[cur].r].cnt; } LL z_query(int k, int old, int cur, LL L, LL R) {if(L == R) {return (LL)k*(L-L/2);}LL mid = (L + R) / 2;int tmp = node[node[cur].r].cnt - node[node[old].r].cnt;if(k <= tmp) {return z_query(k, node[old].r, node[cur].r, mid + 1, R);}else {return node[node[cur].r].sum - node[node[old].r].sum+ z_query(k-tmp, node[old].l, node[cur].l, L, mid);} } /*LL query(int k, int old, int cur, int L, LL R) {printf("%d %lld %lld\n", k, node[cur].sum, node[old].sum);if(L == R) {printf("*%d %d\n", L,k*(L-L/2));return (LL)k*(L-L/2);}LL mid = (L + R) / 2;int tmp = node[node[cur].r].cnt - node[node[old].r].cnt;printf("%d %d %d %d %lld\n", k, tmp, node[node[old].r].cnt,node[node[cur].r].cnt,node[node[cur].r].sum - node[node[old].r].sum);if(k <= tmp) {return query(k, node[old].r, node[cur].r, mid + 1, R);}else {return node[node[cur].r].sum - node[node[old].r].sum+ query(k-tmp, node[old].l, node[cur].l, L, mid);} }*/ int main(){scanf("%d%d", &n, &q);for(int i = 1; i <= n; ++i) scanf("%d", ar+i), sum[i]=sum[i-1]+ar[i];for(int i = 1; i <= q; ++i) {scanf("%d%d%d", &cw[i].l, &cw[i].r, &cw[i].k);cw[i].ans = sum[cw[i].r] - sum[cw[i].l-1];}LL L, R;for(int T = 30; T >= 0; --T) {L = 1LL<<T, R = 2LL<<T, inde = 0;node[0].l = node[0].r = node[0].sum = node[0].cnt = 0;for(int i = 1; i <= n; ++i) if(ar[i]>>T&1) {z_update(Root[i-1], Root[i], ar[i], L, R);//if(T == 2) printf("[%d %d]\n", i, ar[i]);sum[i] = sum[i-1] + ar[i] - ar[i]/2; num[i] = num[i-1] + 1;}else Root[i] = Root[i-1], sum[i] = sum[i-1], num[i] = num[i-1];//printf("T = %d\n", T);for(int i = 1, tmp; i <= q; ++i) {if(cw[i].k == 0) continue;if(cw[i].k >= num[cw[i].r] - num[cw[i].l-1]) {cw[i].k -= num[cw[i].r] - num[cw[i].l-1];cw[i].ans -= sum[cw[i].r] - sum[cw[i].l-1];}else {//printf("*%lld %d ", cw[i].ans, cw[i].k);cw[i].ans -= z_query(cw[i].k, Root[cw[i].l-1], Root[cw[i].r], L, R);//printf("%lld %d\n", cw[i].ans, T);cw[i].k = 0;}//printf("%d %d %d\n", cw[i].l, cw[i].r, cw[i].k);}for(int i = 1; i <= n; ++i) if(ar[i]>>T&1) ar[i] >>= 1;//printf("***\n");}for(int i = 1; i <= q; ++i) printf("%lld\n", cw[i].ans);return 0; }

5E div1 Fast Kronecker Transform (NTTorFFT)

//E 題解就在這個博客里 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back namespace lh { #define o2(x) (x)*(x)using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, LL> pii; }using namespace lh; const int MX = 2e5 + 5; //const int P = (479 << 21) + 1; const int P = 998244353; const int MOD = 998244353; const int G = 3; const int NUM = 20; struct my_NTT {LL wn[NUM];LL a[MX << 1], b[MX << 1];LL pow (LL a, LL x, LL mod) {LL ans = 1;a %= mod;while (x) {if (x & 1) ans = ans * a % mod;x >>= 1;a = a * a % mod;}return ans;}//在程序的開頭就要放void init() {for (int i = 0; i < NUM; i++) {int t = 1 << i;wn[i] = pow (G, (P - 1) / t, P);}}void Rader (LL F[], int len) {int j = len >> 1;for (int i = 1; i < len - 1; i++) {if (i < j) swap (F[i], F[j]);int k = len >> 1;while (j >= k) j -= k, k >>= 1;if (j < k) j += k;}}void NTT (LL F[], int len, int t) {Rader (F, len);int id = 0;for (int h = 2; h <= len; h <<= 1) {id++;for (int j = 0; j < len; j += h) {LL E = 1;for (int k = j; k < j + h / 2; k++) {LL u = F[k];LL v = E * F[k + h / 2] % P;F[k] = (u + v) % P;F[k + h / 2] = (u - v + P) % P;E = E * wn[id] % P;}}}if (t == -1) {for (int i = 1; i < len / 2; i++) swap (F[i], F[len - i]);LL inv = pow (len, P - 2, P);for (int i = 0; i < len; i++) F[i] = F[i] * inv % P;}}void Conv (LL a[], LL b[], int len) {NTT (a, len, 1);NTT (b, len, 1);for (int i = 0; i < len; i++) a[i] = a[i] * b[i] % P;NTT (a, len, -1);}int gao (LL A[], LL B[], int n, int m, LL ans[]) {//0~n-1int len = 1;while (len < n + m) len <<= 1;for (int i = 0; i < n; i++) a[i] = A[i];for (int i = 0; i < m; i++) b[i] = B[i];for (int i = n; i < len; i++) a[i] = 0;for (int i = m; i < len; i++) b[i] = 0;Conv (a, b, len);for (int i = 0; i < len; i++) ans[i] = (ans[i]+a[i])%MOD;return len;} }ntt; const int MXN = 2e5 + 5; int n, m; int ar[MXN], br[MXN]; LL A[MXN], B[MXN]; std::vector<int> all[MXN], bll[MXN]; LL ans[MXN]; void solve1(int id) {for(int i = 0; i < all[id].size(); ++i) {for(int j = 0; j < bll[id].size(); ++j) {ans[all[id][i]+bll[id][j]] += (LL)all[id][i] * bll[id][j];ans[all[id][i]+bll[id][j]] %= MOD;}} } void solve2(int id) {for(int i = 0; i <= n+m; ++i) A[i] = B[i] = 0;for(int i = 0; i < all[id].size(); ++i) A[all[id][i]] = all[id][i];for(int i = 0; i < bll[id].size(); ++i) B[bll[id][i]] = bll[id][i];int len = ntt.gao(A, B, all[id].back()+1, bll[id].back()+1, ans); } int main(int argc, char const *argv[]) {scanf("%d%d", &n, &m); ++n, ++m;ntt.init();std::vector<int> vs;for(int i = 0; i < n; ++i) scanf("%d", &ar[i]), vs.push_back(ar[i]);for(int i = 0; i < m; ++i) scanf("%d", &br[i]), vs.push_back(br[i]);sort(vs.begin(), vs.end());vs.erase(unique(vs.begin(), vs.end()), vs.end());for(int i = 0, tmp; i < n; ++i) {tmp = lower_bound(vs.begin(), vs.end(), ar[i]) - vs.begin();all[tmp].push_back(i);}for(int i = 0, tmp; i < m; ++i) {tmp = lower_bound(vs.begin(), vs.end(), br[i]) - vs.begin();bll[tmp].push_back(i);}for(int i = 0; i < vs.size(); ++i) {if(all[i].size() + bll[i].size() <= 10000) solve1(i);else solve2(i);}for(int i = 0; i <= n + m-2; ++i) printf(i!=n+m-2?"%lld ":"%lld\n", ans[i]);return 0; }

day7

7G div1&2 搶紅包機器人 (拓撲序)

//G #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 2e2 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, m; int ar[MXN][MXN], pos[MXN][MXN]; int vis[MXN], far[MXN], is[MXN], id[MXN]; int flag; std::vector<int> mp[MXN]; void dfs(int u,int ba) {vis[u] = 1;flag ++;for(auto v: mp[u]) {if(vis[v]) continue;dfs(v, u);} } int main(){scanf("%d%d", &n, &m);queue<int> Q;for(int i = 1, k; i <= m; ++i) {scanf("%d", &k);ar[i][0] = k;for(int j = 1, x; j <= k; ++j) {scanf("%d", &ar[i][j]);is[ar[i][j]] = 1;}}int cnt = INF;for(int i = 1; i <= m; ++i) {for(int j = 2; j <= ar[i][0]; ++j) {mp[ar[i][j]].push_back(ar[i][j-1]);}}for(int i = 1; i <= n; ++i) {flag = 0;memset(vis, 0, sizeof(vis));dfs(i, i);cnt = min(cnt, flag);}printf("%d\n", cnt);return 0; }

7A div1 迷宮 (樹 規律)

//A #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, LL> pii;const int MXN = 2e5 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, m; std::vector<int> mp[MXN]; int is[MXN], dep[MXN],dp[MXN], ans; void dfs(int u,int ba,int d) {int sum = 0;if(is[u]) dep[d] ++;m = max(m, d);for(auto v: mp[u]) {if(v == ba) continue;dfs(v, u, d + 1);} } int main(){scanf("%d", &n);for(int i = 1; i <= n; ++i) scanf("%d", &is[i]);for(int i = 1, a, b; i < n; ++i) {scanf("%d%d", &a, &b);mp[a].push_back(b);mp[b].push_back(a);}dfs(1, 1, 0);for(int i = 1; i <= 2*n; ++i) {//ans += max(dep[i]-1,0);if(dep[i] >= 2) {dep[i+1] += dep[i]-1;}if(dep[i]) ans = i;}printf("%d\n", ans);return 0; }

7E div2 線性探查法 (暴力)

//E #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, int> pii;const int MXN = 2e3 + 6; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n, m; int ar[MXN], br[MXN], ans[MXN], is[MXN]; int main(){scanf("%d", &n);std::vector<pii> dai;for(int i = 0; i < n; ++i) scanf("%d", &br[i]), dai.push_back({br[i],i});memset(ans, -1, sizeof(ans));int cnt = 1;while(cnt <= n) {int MMIN = INF, pos = -1, ers;//printf("cnt = %d\n", cnt);for(int i = 0; i < dai.size(); ++i) {int tmp = dai[i].fi % n;while(ans[tmp] != -1) {tmp = (tmp + 1) % n;}//printf("*%d %d %d\n", dai[i].fi, tmp, dai[i].se);if(tmp == dai[i].se) {if(MMIN > dai[i].fi) {MMIN = dai[i].fi;pos = tmp;ers = i;}}}//printf("--%d %d\n", MMIN, pos);if(cnt != n) printf("%d ", MMIN);else {printf("%d\n", MMIN);break;}ans[pos] = MMIN;for(int i = ers; i < dai.size() - 1; ++i) {dai[i] = dai[i+1];}dai.resize(dai.size()-1);cnt ++;}return 0; }

7C div1 斐波那契數列 (打表找規律)

//C #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, int> pii;const int MXN = 2e5 + 6; const int INF = 0x3f3f3f3f; const LL mod = 998244353; LL n, m; typedef vector<long long> vec; typedef vector<vec > mat;mat Mul(mat a, mat b) {mat c(a.size(), vec(b[0].size()));for(int k = 0; k < b.size(); ++k) {for(int i = 0; i < a.size(); ++i) {if(a[i][k] == 0) continue;for(int j = 0; j < b[0].size(); ++j) {c[i][j] = (c[i][j] + a[i][k] * b[k][j])%mod;}}}return c; } mat mat_ksm(mat a, LL b) {mat res(a.size(), vec(a.size()));for(int i = 0; i < a.size(); ++i) res[i][i] = 1;while(b) {if(b&1) res = Mul(res, a);a = Mul(a, a);b >>= 1;}return res; } LL fib_n(LL n) {mat a(2, vec(2));a[0][0] = 1; a[0][1] = 1;a[1][0] = 1; a[1][1] = 0;a = mat_ksm(a, n);return a[1][0]; } LL getnum(LL n) {LL ans = n - n/3, now = 2;n /= 3;while(n) {ans = (ans + (n+1)/2*now%mod)%mod;n /= 2;if(now == 2) now = 8;else now = now*2%mod;}return ans; } int main(){int tim; scanf("%d", &tim);while(tim --) {scanf("%lld", &n);if(n <= 2) {printf("0\n");continue;}LL ans = (fib_n(n+2) - 1 + mod)%mod;printf("%lld\n", (ans - getnum(n) + mod)%mod);}return 0; }

7F div2 逆序對！ (規律)

//F //假設a > b且a^b的最高位是第i位, 則a^s > b^s的條件是s的第i位為0. #include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define pb push_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, int> pii;const int MXN = 1e5 + 6; const int INF = 0x3f3f3f3f; const LL mod = 998244353;int n, m; LL ar[MXN]; LL dp[55][2][55][2]; LL two[55], my[55][2], num[55]; std::vector<int> vs; int solve(int tn) {while(tn) {vs.push_back(tn&1);tn >>= 1;}int cnt = 1;LL T = 1;for(auto x: vs) {num[cnt] = num[cnt-1]+T*x;++ cnt; T *= 2;}reverse(vs.begin(), vs.end());LL zhi = vs[0];int len = vs.size();my[1][0] = (two[len-1] - 1 + mod) % mod;my[1][1] = m - (1LL<<(len-1)) + 1;assert(my[1][0]+my[1][1] == m);for(int i = 1; i < len; ++i) {if(vs[i]) {my[i+1][1] = num[len-i-1] + 1 + (zhi)*two[len-i-1];my[i+1][0] = (zhi+1)*two[len-i-1] - 1;}else {my[i+1][1] = (zhi)*two[len-i-1];my[i+1][0] = num[len-i-1] + 1 + (zhi)*two[len-i-1] - 1;}my[i+1][1] = (my[i+1][1]%mod + mod)%mod;my[i+1][0] = (my[i+1][0]%mod + mod)%mod;assert(my[i][0]+my[i][1] == m);zhi = zhi * 2 + vs[i];}return len; } int get(LL NUM) {int x = 0;while(NUM) {++ x;NUM /= 2;}return x; } int main(){scanf("%d%d", &n, &m);two[0] = 1; for(int i = 1; i <= 32; ++i) two[i] = two[i-1] * 2 % mod;int len = solve(m);for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);if(n == 1) {printf("0\n");return 0;}LL ANS = 0, temp;for(int i = 1; i < n; ++i) {for(int j = i + 1; j <= n; ++j) {int tmp = get(ar[i]^ar[j]); temp = 0;if(ar[i] > ar[j]) {if(tmp > len) temp = m;else temp = my[len-tmp+1][0];}else {if(tmp <= len) temp = my[len-tmp+1][1];}ANS = (ANS + temp + mod)%mod;}}printf("%lld\n", ANS%mod);return 0; } 這個題也可以跑數位dp，比如這樣： LL solve(int id, int ip, int pos, int pre, bool zero, bool limit) {//第id位必須為ip的方案數if(pos == -1) {if(zero) return 0;return 1;}if(!limit&&!zero&&dp[id][ip][pos][pre]!=-1) return dp[id][ip][pos][pre];int up = limit?num[pos]:1, low = 0;LL sum = 0;if(pos == id) {if(limit && num[pos] == 0 && ip == 1) return 0;up = low = ip;}for(int i = low; i <= up; ++i) {sum += solve(id, ip, pos-1, i, zero&&i==0,limit&&i==num[pos]);}if(!limit&&!zero) dp[id][ip][pos][pre] = sum;return sum; }

7J div1&2 強壯的排列

/* 題意： T(1e4),n(1e5)奇數 問有多少個長度為n的排列滿足一下條件： (1<=x<=n/2) p[2*x]=max(p[2*x-1],p[2*x+1]) 題解： https://www.90yang.com/category/algorithm/ https://blog.csdn.net/nike0good/article/details/86662644 */ //oeis解法 //n%4==0和n=1時Bnl[n]是負的 //a(n) = abs[c(2*n-1)] where c(n)= 2^(n+1) * (1-2^(n+1)) * Ber(n+1)/(n+1) //a(n) = 2^(2*n) (2^(2*n) - 1) |B_(2*n)| #include<bits/stdc++.h> #pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; const int mod = 998244353; namespace BNL{using namespace std;const int N = 300020;//const LL P = 50000000001507329LL; //190734863287 * 2 ^ 18 + 1 G = 3 常數巨大//const int P = 1004535809; //479 * 2 ^ 21 + 1 G = 3const int P = 998244353; // 119 * 2 ^ 23 + 1 G = 3//const int P = 104857601; // 25 * 2 ^ 22 + 1 G = 3//const int P = 167772161; // 5 * 2 ^ 25 + 1 G = 3const int G = 3;int wn[25];LL mul(LL x, LL y) {return (x * y - (LL)(x / (long double)P * y + 1e-3) * P + P) % P;}LL qpow(LL a, int b, int mod=P) {LL res = 1;for(;b;b>>=1,a=a*a%mod) {if(b&1) res=res*a%mod;}return res;}void getwn() {for(int i = 1; i <= 21; ++i) {int t = 1 << i;wn[i] = qpow(G, (P - 1) / t, P);}}void change(int *y, int len) {for(int i = 1, j = len / 2; i < len - 1; ++i) {if(i < j) swap(y[i], y[j]);int k = len / 2;while(j >= k) {j -= k;k /= 2;}j += k;}}void NTT(int *y, int len, int on) {change(y, len);int id = 0;for(int h = 2; h <= len; h <<= 1) {++id;for(int j = 0; j < len; j += h) {int w = 1;for(int k = j; k < j + h / 2; ++k) {int u = y[k];int t = 1LL * y[k+h/2] * w % P;y[k] = u + t;if(y[k] >= P) y[k] -= P;y[k+h/2] = u - t + P;if(y[k+h/2] >= P) y[k+h/2] -= P;w = 1LL * w * wn[id] % P;}}}if(on == -1) {for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]);int inv = qpow(len, P - 2, P);for(int i = 0; i < len; ++i)y[i] = 1LL * y[i] * inv % P;}}int tmp[N];void get_inv(int A[], int A0[], int t) {if(t == 1) {A0[0] = qpow(A[0], P - 2, P);return;}get_inv(A, A0, t / 2);for(int i = 0; i < t; ++i) tmp[i] = A[i];for(int i = t; i < 2 * t; ++i) tmp[i] = 0;for(int i = t / 2; i < 2 * t; ++i) A0[i] = 0;NTT(tmp, 2 * t, 1);NTT(A0, 2 * t, 1);for(int i = 0; i < 2 * t; ++i) {tmp[i] = (2 - 1LL * tmp[i] * A0[i] % P) % P;if(tmp[i] < 0) tmp[i] += P;A0[i] = 1LL * A0[i] * tmp[i] % P;}NTT(A0, 2 * t, -1);}int B[N], f[N], nf[N], a[N];void init() {f[0] = 1;for(int i = 1; i < N; ++i) f[i] = 1LL * f[i-1] * i % P;nf[N-1] = qpow(f[N-1], P - 2, P);for(int i = N - 2; i >= 0; --i) {nf[i] = 1LL * nf[i+1] * (i + 1) % P;}for(int i = 0; i < N - 1; ++i) a[i] = nf[i+1];int len = 1 << 17;get_inv(a, B, len);for(int i = 0; i < len; ++i) B[i] = 1LL * B[i] * f[i] % P;}void solve_bnl() {getwn();//最前面init();} } using namespace BNL;LL solve(int n) {return 1LL*(1-qpow(2,n+1))%mod*qpow(2,n+1)%mod*B[n+1]%mod*qpow(n+1,mod-2)%mod; } int main() {solve_bnl();for(int i = 0; i <= 20; ++i) printf("%d\n", B[i]);int tim; scanf("%d", &tim);while(tim --) {//n為奇數,1,3,5...int n; scanf("%d", &n); n = (n+1)/2;n = 2*n-1;LL ans = (solve(n)+mod)%mod;if(n+1 >= 1)ans = (mod-ans)%mod;if((n+1)%4==0 || n+1==1) ans = (mod-ans);printf("%lld\n", ans);}return 0; }

7H div2 同構 整數劃分

#include<bits/stdc++.h> #define fi first #define se second #define iis std::ios::sync_with_stdio(false) #define eb emplace_back #define o2(x) (x)*(x) using namespace std; typedef long long LL; typedef pair<int, int> pii;const int mod = 998244353; int n; LL dp[1005][1005];LL q(int n,int m){if(dp[n][m] != -1) return dp[n][m];if(n == 3) return 1;else if(n < 3) return 0;if(m < 3) return 0;LL sum = 0;if(n < m) sum = q(n,n); if(n == m) sum = q(n,m-1)+1; if(n>m) sum = (q(n,m-1) + q(n-m,m))%mod;dp[n][m] = sum;return dp[n][m]; }int main(){memset(dp, -1, sizeof(dp));scanf("%d",&n); if(n <= 5) {printf("1\n");}else printf("%lld\n",q(n,n)%mod); return 0; }

7H div1 同構 整數劃分

五邊形數

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 8; const int mo = 998244353; typedef long long LL; LL dp[N]; int main(){int n = 1e5+1;dp[0] = 1;for (int i = 1; i <= n; ++i){for (LL j = 1, tmp = 1; i >= (3 * j * j - j) / 2; ++j, tmp *= -1){LL x = (3 * j * j - j) / 2;LL y = (3 * j * j + j) / 2;dp[i] = ((dp[i] + tmp * dp[i - x]) % mo + mo) % mo;if (i >= y) dp[i] = ((dp[i] + tmp * dp[i - y]) % mo + mo) % mo;}}scanf("%d", &n);if(n < 3) printf("0\n");else if(n == 3) printf("1\n");else printf("%lld\n", ((((dp[n]-dp[n-1])%mo-dp[n-2])%mo+dp[n-3])%mo+mo)%mo);return 0; } #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int mul(int a, int b, int mod){ return (long long)a*b%mod; } int power(int a, int b, int mod){int ret = 1;for (int t = a; b; b >>= 1){if (b & 1)ret = mul(ret, t, mod);t = mul(t, t, mod);}return ret; } int cal_root(int mod) {int factor[20], num = 0, m = mod - 1, s = m;for (int i = 2; i * i <= s; i++){if (s % i == 0){factor[num++] = i;while (s % i == 0)s /= i;}}if (s != 1)factor[num++] = s;for (int i = 2;; i++){int j = 0;for (; j < num && power(i, m / factor[j], mod) != 1; j++);if (j == num)return i;} } template<int MOD, int ROOT> void fft_main(int a[], int len, bool reverse) {for (int i = 1, j = len / 2; i < len - 1; i++) {if (i < j) swap(a[i], a[j]);for (int k = len; j < k; k >>= 1, j ^= k);}for (int s = 1; s < len; s <<= 1){int t = (MOD - 1) / (s * 2);int step = power(ROOT, reverse ? MOD - 1 - t : t, MOD);for (int j = 0; j < len; j += 2 * s){int cur = 1;for (int k = j; k < j + s; k++){int u = a[k], t = mul(cur, a[k + s], MOD);a[k] = (unsigned int)(u + t) % MOD;a[k + s] = (unsigned int)(u - t + MOD) % MOD;cur = mul(cur, step, MOD);}}}if (reverse){int t = power(len, MOD - 2, MOD);for (int i = 0; i < len; i++)a[i] = mul(a[i], t, MOD);} } //確保數組中的數小于mod(mod<2^30)，數組需留足2^(logn向上取整+1)的空間 //并且mod為形如m*2^k+1的素數，2^k>=2*n template<int MOD, int ROOT> void fft(int a[], int b[], int n){int len = 1;while (len < 2 * n)len <<= 1;memset(a + n, 0, sizeof(int)*(len - n));memset(b + n, 0, sizeof(int)*(len - n));fft_main<MOD, ROOT>(a, len, 0);fft_main<MOD, ROOT>(b, len, 0);for (int i = 0; i < len; i++)a[i] = mul(a[i], b[i], MOD);fft_main<MOD, ROOT>(a, len, 1); }#define MAXN 131072 int par[2*MAXN]; int dp2[2*MAXN],dp[350][MAXN]; template<int MOD, int ROOT> void calParNumber(int n){int s=sqrt(n)+1;par[0]=1;for(int i=3;i<s;i++){for(int j=i;j<=n;j++)(par[j]+=par[j-i])%=MOD;}dp[0][0]=1;dp2[0]=1;for(int i=1;i<=s;i++){for(int j=s;j<=n;j++){dp[i][j]=(dp[i-1][j-s]+dp[i][j-i])%MOD;(dp2[j]+=dp[i][j])%=MOD;}}fft<MOD,ROOT>(par,dp2,n+1); } int main(){calParNumber<998244353,3>(100000);int n;scanf("%d",&n);printf("%d",par[n]); }

day8

8G div1&2 穗乃果的考試 (計數)

//div1G 題解：https://blog.csdn.net/qq_39599067/article/details/86713379 #include<bits/stdc++.h> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXN = 2e3 + 7; const LL mod = 998244353; int n, m; int ar[MXN][MXN]; LL sum[MXN][MXN], sum1[MXN][MXN], sum2[MXN][MXN], sum3[MXN][MXN],sum4[MXN][MXN]; LL up[MXN][MXN], Left[MXN][MXN], Right[MXN][MXN], down[MXN][MXN]; char s[MXN]; int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i) {scanf("%s", s+1);for(int j = 1; j <= m; ++j) ar[i][j] = s[j] - '0';}for(int i = 1; i <= n; ++i) {for(int j = 1, tmp; j <= m; ++j) {if(ar[i][j] == 0) tmp = 0;else tmp = i*j;sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+tmp;sum[i][j] = (sum[i][j]%mod+mod)%mod;}}for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) sum1[i][j] = sum[i-1][j-1];memset(sum, 0, sizeof(sum));for(int i = 1; i <= n; ++i) {for(int j = m, tmp; j >= 1; --j) {if(ar[i][j] == 0) tmp = 0;else tmp = i*(m-j+1);sum[i][j] = sum[i-1][j]+sum[i][j+1]-sum[i-1][j+1]+tmp;sum[i][j] = (sum[i][j]%mod+mod)%mod;}}for(int i = 1; i <= n; ++i) for(int j = m; j >= 1; --j) sum2[i][j] = sum[i-1][j+1];memset(sum, 0, sizeof(sum));for(int i = n; i >= 1; --i) {for(int j = 1, tmp; j <= m; ++j) {if(ar[i][j] == 0) tmp = 0;else tmp = (n-i+1)*j;sum[i][j] = sum[i+1][j]+sum[i][j-1]-sum[i+1][j-1]+tmp;sum[i][j] = (sum[i][j]%mod+mod)%mod;}}for(int i = n; i >= 1; --i) for(int j = 1; j <= m; ++j) sum3[i][j] = sum[i+1][j-1];memset(sum, 0, sizeof(sum));for(int i = n; i >= 1; --i) {for(int j = m, tmp; j >= 1; --j) {if(ar[i][j] == 0) tmp = 0;else tmp = (n-i+1)*(m-j+1);sum[i][j] = sum[i+1][j]+sum[i][j+1]-sum[i+1][j+1]+tmp;sum[i][j] = (sum[i][j]%mod+mod)%mod;}}for(int i = n; i >= 1; --i) for(int j = m; j >= 1; --j) sum4[i][j] = sum[i+1][j+1];for(int i = 2; i <= n; ++i) {for(int j = 1, tmp; j <= m; ++j) {if(ar[i-1][j] == 0) tmp = 0; else tmp = (i-1)*j;up[i][j] = up[i-1][j] + tmp;up[i][j] %= mod;}}for(int i = 1; i <= n; ++i) {for(int j = 2, tmp; j <= m; ++j) {if(ar[i][j-1] == 0) tmp = 0; else tmp = i*(j-1);Left[i][j] = Left[i][j-1] + tmp;Left[i][j] %= mod;}}for(int i = 1; i <= n; ++i) {for(int j = m - 1, tmp; j >= 1; --j) {if(ar[i][j+1] == 0) tmp = 0; else tmp = (n-i+1)*(m-j);Right[i][j] = Right[i][j+1] + tmp;Right[i][j] %= mod;}}for(int i = n-1; i >= 1; --i) {for(int j = 1, tmp; j <= m; ++j) {if(ar[i+1][j] == 0) tmp = 0; else tmp = (n-i)*(m-j+1);down[i][j] = down[i+1][j] + tmp;down[i][j] %= mod;}}LL ans = 0;for(LL i = 1; i <= n; ++i) {for(LL j = 1; j <= m; ++j) {if(ar[i][j] == 0) continue;ans = (ans + i*j%mod*(n-i+1)%mod*(m-j+1)%mod) % mod;ans = (ans + (sum1[i][j]+up[i][j]+Left[i][j])%mod*(n-i+1)%mod*(m-j+1)%mod)%mod;ans = (ans + (Right[i][j]+down[i][j]+sum4[i][j])%mod*i%mod*j%mod)%mod;ans = (ans + sum2[i][j]*(n-i+1)%mod*j%mod+sum3[i][j]*(m-j+1)%mod*i%mod)%mod;}}printf("%lld\n", (ans+mod)%mod);return 0; } //div2G #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii;const int INF = 0x3f3f3f3f; const int MXN = 1e6 + 6; const LL mod = 998244353; LL san[33]; LL dp[44][44][3][44]; int ar[2005][2005]; char s[2005]; LL o2(LL x, LL y) {return (x*(x+1)/2)*(y*(y+1)/2)%mod; } int main() {LL n, m;scanf("%lld%lld", &n, &m);LL ans = 0;for(LL i = 1; i <= n; ++i) {scanf("%s", s+1);for(LL j = 1; j <= m; ++j) {int x = s[j]-'0';if(x == 0) continue;ans += o2(n,m) - o2((i-1),m) - o2((n-i),m) - o2((j-1),n) - o2((m-j),n);ans += o2((i-1),(j-1))+o2((i-1),(m-j))+o2((n-i),(j-1))+o2((n-i),(m-j));ans = (ans % mod + mod) % mod;}}printf("%lld\n", ans);return 0; }

8D div2 吉良吉影的奇妙計劃 (dp)

//D #include<bits/stdc++.h> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXN = 4e1 + 7; const LL mod = 998244353; int n, m; LL dp[MXN][MXN][MXN][3]; int main() {scanf("%d", &n); n <<= 1;dp[1][1][0][1] = 1;dp[1][0][1][2] = 1;dp[2][1][1][0] = 1;for(int i = 1; i <= n; ++i) {for(int x = 0; x <= i; ++x) {for(int y = 0; y + x <= i; ++y) {dp[i+2][x+1][y+1][0] = (dp[i][x][y][1] + dp[i][x][y][2])%mod;dp[i+1][x+1][y][1] = (dp[i][x][y][1] + dp[i][x][y][0])%mod;dp[i+1][x][y+1][2] = (dp[i][x][y][2] + dp[i][x][y][0])%mod;}}}LL ans = (dp[n][n/2][n/2][0]+dp[n][n/2][n/2][1]+dp[n][n/2][n/2][2]) % mod;printf("%lld\n", ans);return 0; } /* id = 0表示空白 id = 1表示左 id = 2表示右 dp[i][x][y][id]到第i天選了x個左y個右最后一個是id的方案數 人人為我: dp[i][x][y][0] = dp[i-2][x-1][y-1][1] + dp[i-2][x-1][y-1][2]; dp[i][x][y][1] = dp[i-1][x-1][y][1] + dp[i-1][x-1][y][2] + dp[i-1][x-1][y][0]; dp[i][x][y][2] = dp[i-1][x][y-1][2] + dp[i-1][x][y-1][0]; 我為人人: dp[i+2][x+1][y+1][0] = dp[i][x][y][1] + dp[i][x][y][2]; dp[i+1][x+1][y][1] = dp[i][x][y][1] + dp[i][x][y][2] + dp[i][x][y][0]; dp[i+1][x][y+1][2] = dp[i][x][y][2] + dp[i][x][y][0]; */

8A div1 Aqours (性質 dp)

//A #include<bits/stdc++.h> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MX = 4e6 + 7; int n; vector<int> cw[MX]; vector<int> vs; int vis[MX]; int mp[MX];int D, ANS; inline int upup(int u, int d) {if(vis[u]) {ANS = d + vis[u];return vis[u];}vis[u] = d;int T = upup(mp[u], d+1);vis[u] = min(vis[u], T + 1);return vis[u]; } int main() {scanf("%d", &n);if(n == 1) {printf("1 -1\n");return 0;}for(int i = 2, u; i <= n; ++i) {scanf("%d", &u);cw[u].push_back(i);mp[i] = u;}for(int i = 1;i <= n;i++) if(cw[i].size() == 0) vs.push_back(i);sort(vs.begin(), vs.end());printf("%d -1\n", vs[0]);vis[0] = 1e8;upup(vs[0], 0);for(int i = 1; i < vs.size(); ++i) {upup(vs[i], 0);printf("%d %d\n", vs[i], ANS);//io.wint(vs[i],0);io.wint(len+D,1);}return 0; }

8B div1 玖凜兩開花 (匈牙利+枚舉or二分)

#include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXN = 2e4 + 7; const LL mod = 998244353; int n, m; struct lp {int u, v; }cw[MXN]; std::vector<int> son[MXN]; int vis[MXN], be[MXN], is[MXN]; int L; bool dfs(int u){for(auto x : son[u]){if(x < L) continue;if(vis[x]) continue;vis[x] = 1;if(is[x] == -1 || dfs(is[x])){is[x] = u;be[u] = x;return true;}}return false; } int main() {scanf("%d%d", &n, &m);for(int i = 0; i < m; ++i) {scanf("%d%d", &cw[i].u, &cw[i].v);cw[i].u++; cw[i].v++;if(cw[i].u > cw[i].v) swap(cw[i].u, cw[i].v);son[cw[i].u].push_back(cw[i].v);}for(int i = 1; i <= n; ++i) is[i] = be[i] = -1;int ans = 1;for(int i = 1; i <= n; ++i) {L = i + 1;if(is[i] != -1) {for(int j = 1; j <= n; ++j) vis[j] = 0;if(!dfs(is[i])) break;is[i] = -1;}for(int j = 1; j <= n; ++j) vis[j] = 0;if(dfs(i)) ++ ans;else break;}printf("%d\n", ans - 1);return 0; } /* 考慮二分答案是否>= x，可以把圖變成一個二分圖，左邊是< x的，右邊是>= x的。在原圖中兩部分 內部是可能有邊的，但是選出這些邊不會對“答案能達到x”更有利，所以這些邊忽略即可。然后可以用匈 牙利算法檢查是否左邊的點是否全部都能匹配上。時間復雜度O(nmlogn)，因為匈牙利算法很難卡到上 限O(nm)且常數很小，所以也能通過。 實際上二分答案的過程可以去掉。我們考慮把二分的過程變成從小到大枚舉，到x + 1的時候就是把x點 加入二分圖的左邊。如果x之前在右邊的時候和某個左邊的點v匹配過了，把這個匹配關系拆掉，把v再 匹配一遍就可以了。時間復雜度O(nm)。 如果用Dinic或者HK的話，時間復雜度可以做到O(m√n)。 */ //二分+dinic #include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXAN = 2e4 + 7; const LL mod = 998244353; int n, m; struct lp {int u, v; }cw[MXAN]; const int INF = 0x3f3f3f3f; const int MXN = 1e4+7; const int MXE = 1e6+7; struct DINIC{int tot,vt,vs;int d[MXN],head[MXN];struct lp{int v,w,nex;}cw[MXE];void add_edge(int a,int b,int c){cw[++tot].v=b;cw[tot].nex=head[a],cw[tot].w=c;head[a]=tot;cw[++tot].v=a;cw[tot].nex=head[b],cw[tot].w=0;head[b]=tot;}bool bfs(){memset(d,-1,sizeof(d));queue<int>Q;Q.push(vt);d[vt]=0;while(!Q.empty()){int u=Q.front();Q.pop();for(int i=head[u];i!=-1;i=cw[i].nex){int v=cw[i].v;if(cw[i^1].w&&d[v]==-1){d[v]=d[u]+1;Q.push(v);}}}return d[vs]!=-1;}int dfs(int x,int low){if(x==vt||low==0)return low;int flow=0,used=0;for(int i=head[x];i!=-1;i=cw[i].nex){int v=cw[i].v;if(cw[i].w&&d[v]+1==d[x]&&(used=dfs(v,min(low,cw[i].w)))>0){//used=dfs(v,min(low,cw[i].w));if(!used)continue;flow+=used,low-=used;cw[i].w-=used;cw[i^1].w+=used;if(!low)break;}}if(!flow)d[x]=-1;return flow;}void init(int st,int ed){tot=-1;for(int i = st; i <= ed; ++i) head[i] = -1;vs=st;vt=ed;}int max_flow(){int ans=0;while(bfs())ans+=dfs(vs,INF);return ans;} }dinic; int vs, vt; bool ok(int mid) {vs = 0, vt = n + 1;dinic.init(vs, vt);for(int i = 1; i < mid; ++i) dinic.add_edge(vs, i, 1);for(int i = mid; i <= n; ++i) dinic.add_edge(i, vt, 1);for(int i = 0; i < m; ++i) {if(cw[i].v >= mid && cw[i].u < mid) {dinic.add_edge(cw[i].u, cw[i].v, 1);}}return dinic.max_flow() == mid-1; } int main() {scanf("%d%d", &n, &m);for(int i = 0; i < m; ++i) {scanf("%d%d", &cw[i].u, &cw[i].v);cw[i].u++; cw[i].v++;if(cw[i].u > cw[i].v) swap(cw[i].u, cw[i].v);}int L = 1, R = n, mid, ans = 0;while(L <= R) {mid = (L + R) >> 1;if(ok(mid)) ans = mid, L = mid + 1;else R = mid - 1;}printf("%d\n", ans-1);return 0; } //二分+匈牙利 #include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXN = 2e4 + 7; const LL mod = 998244353; int n, m; struct lp {int u, v; }cw[MXN]; std::vector<int> son[MXN]; int vis[MXN], be[MXN], is[MXN]; bool dfs(int u){for(auto x : son[u]){if(vis[x]) continue;vis[x] = 1;if(is[x] == -1 || dfs(is[x])){is[x] = u;be[u] = x;return true;}}return false; } bool ok(int mid) {for(int i = 1; i <= n; ++i) son[i].clear();for(int i = 0; i < m; ++i) {if(cw[i].v >= mid && cw[i].u < mid) {son[cw[i].u].push_back(cw[i].v);}}for(int i = 1; i <= n; ++i) is[i] = be[i] = -1;int cnt = 0;for(int i = 1; i <= n; ++i){if(be[i] != -1) continue;for(int j = 1; j <= n; ++j) vis[j] = 0;if(dfs(i)) cnt++;}return cnt == mid-1; } int main() {scanf("%d%d", &n, &m);for(int i = 0; i < m; ++i) {scanf("%d%d", &cw[i].u, &cw[i].v);cw[i].u++; cw[i].v++;if(cw[i].u > cw[i].v) swap(cw[i].u, cw[i].v);}int L = 1, R = n, mid, ans = 0;while(L <= R) {mid = (L + R) >> 1;if(ok(mid)) ans = mid, L = mid + 1;else R = mid - 1;}printf("%d\n", ans-1);return 0; } //

8E div2 Souls-like Game (矩陣乘法 優化)

//vector被卡常數了，死活過不去臥槽 //div2就是一個矩陣乘法，div1要用線段樹優化一下 //不過說實話，這個n*m*9的復雜度能過這一題，我也是醉了 #include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL; const int MXN = 1e4 + 7; const LL mod = 998244353; int n, m; LL sum[2][3]; int ar[MXN][3][3], tmp[3][3]; int main() {scanf("%d%d", &n, &m);for(int i = 1; i < n; ++i) {for(int j = 0; j < 3; ++j) {for(int k = 0; k < 3; ++k) {scanf("%d", &ar[i][j][k]);}}}int opt, l, r;while(m --) {scanf("%d%d%d", &opt, &l, &r);if(opt == 1) {for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) scanf("%d", &tmp[i][j]);for(int i = l; i <= r; ++i) for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k) {ar[i][j][k] = tmp[j][k];}}else {opt = 1;sum[0][0] = sum[0][1] = sum[0][2] = 1;for(int i = l; i < r; ++i) {for(int j = 0; j < 3; ++j) sum[opt][j] = 0;for(int k = 0; k < 3; ++k) {for(int j = 0; j < 3; ++j) {sum[opt][j] = (sum[opt][j]+sum[opt^1][k]*ar[i][k][j])%mod;}}opt ^= 1;}printf("%lld\n", (sum[opt^1][0]+sum[opt^1][1]+sum[opt^1][2])%mod);}}return 0; }

8E div1 Souls-like Game (線段樹+矩陣乘法)

//哇，這題ac完感覺好爽啊 //第一次寫這種結構體線段樹還重載操作符的，舒服 //沒有人寫博客，只能看著官方題解意會解法 #include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL;const int MXN = 2e5 + 7; const LL mod = 998244353;int n, m, Q; int ar[MXN][3][3], two[33]; int lazy[MXN<<2][3][3], flag[MXN<<2]; map<int, int> mp;struct edge {int opt, l, r;int ar[3][3]; }node[MXN]; struct lp {int sum[3][3];friend lp operator *(const lp&a, const lp&b) {lp c;clr(c.sum, 0);for(int k = 0; k < 3; ++k) for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) {c.sum[i][j] = (c.sum[i][j]+(LL)a.sum[i][k]*b.sum[k][j])%mod;}return c;} }cw[MXN<<2], tp[MXN][33];void push_up(int rt) {cw[rt] = cw[lson] * cw[rson]; } void build(int l,int r,int rt) {flag[rt] = -1;if(l == r) {for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) cw[rt].sum[i][j] = ar[l][i][j];return ;}int mid = (l + r) >> 1;build(l, mid, lson); build(mid+1,r,rson);push_up(rt); } void push_down(int l,int mid,int r,int rt) {if(flag[rt] == -1) return;flag[lson] = flag[rson] = flag[rt];for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[lson][i][j] = lazy[rt][i][j], lazy[rson][i][j] = lazy[rt][i][j];cw[lson] = tp[flag[rt]][mp[mid-l+1]-1];cw[rson] = tp[flag[rt]][mp[r-mid]-1];assert(mp[mid-l+1]); assert(mp[r-mid]);flag[rt] = -1; } void update(int L,int R,int id,int l,int r,int rt) {if(L <= l && r <= R) {flag[rt] = id;for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) lazy[rt][i][j] = node[id].ar[i][j];assert(mp[r-l+1]);cw[rt] = tp[id][mp[r-l+1]-1];return ;}int mid = (l + r) >> 1;push_down(l, mid, r, rt);if(L > mid) update(L, R, id, mid+1, r, rson);else if(R <= mid) update(L, R, id, l, mid, lson);else {update(L,mid,id,l,mid,lson); update(mid+1,R,id,mid+1,r,rson);}push_up(rt); } lp query(int L,int R,int l,int r,int rt) {if(L <= l && r <= R) {return cw[rt];}int mid = (l + r) >> 1;push_down(l, mid, r, rt);if(L > mid) return query(L, R, mid+1, r, rson);else if(R <= mid) return query(L, R, l, mid, lson);else {return query(L,mid,l,mid,lson)*query(mid+1,R,mid+1,r,rson);} } int main() {two[0] = 1, mp[1] = 1;for(int i = 1; i <= 17; ++i) two[i] = two[i-1] << 1, mp[1<<i] = i + 1;//printf("%d %d\n", two[17], mp[1<<17]-1);scanf("%d%d", &n, &Q);for(int i = 1; i < n; ++i) {for(int j = 0; j < 3; ++j) for(int k = 0; k < 3; ++k) scanf("%d", &ar[i][j][k]);}m = 2;while(m < n) m <<= 1;build(1, m, 1);int opt, l, r;for(int i = 1; i <= Q; ++i) {scanf("%d%d%d", &node[i].opt, &node[i].l, &node[i].r);if(node[i].opt == 1) {for(int k = 0; k < 3; ++k) for(int j = 0; j < 3; ++j) {scanf("%d", &node[i].ar[k][j]);tp[i][0].sum[k][j] = node[i].ar[k][j];}for(int k = 1; k <= 17; ++k) {tp[i][k] = tp[i][k-1] * tp[i][k-1];}/*printf("***\n");for(int h = 0; h < 3; ++ h) {for(int k = 0; k < 3; ++k) {for(int j = 0; j < 3; ++j) {printf("%d ", tp[i][h].sum[k][j]);}printf("\n");}}*/update(node[i].l, node[i].r, i, 1, m, 1);}else {LL ans = 0;lp a = query(node[i].l, node[i].r-1, 1, m, 1);for(int i = 0; i < 3; ++i) for(int j = 0; j < 3; ++j) ans = (ans + a.sum[i][j]) % mod;printf("%lld\n", ans);}}return 0; }

8I div1 岸邊露伴的人生經驗 (FWT)

//題解 https://blog.csdn.net/qq_39599067/article/details/86747863 #include<bits/stdc++.h> #define clr(a, b) memset(a,b,sizeof((a))) #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long LL;const int MXN = 3e5 + 7; const int MOD = 998244353; int n, m, Q; int LN; LL ar[1<<21], br[MXN], inv2; LL ksm(LL a, int b) {LL res = 1;for(; b; b>>=1, a=a*a%MOD) {if(b&1) res = res * a % MOD;}return res; } void FWT_xor(LL *a,int LN,int opt) {for(int i=1;i<LN;i<<=1)for(int p=i<<1,j=0;j<LN;j+=p)for(int k=0;k<i;++k) {LL X=a[j+k],Y=a[i+j+k];a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD;if(opt==-1)a[j+k]=a[j+k]*inv2%MOD,a[i+j+k]=a[i+j+k]*inv2%MOD;} } int main() {inv2 = ksm(2, MOD - 2);scanf("%d", &n);for(int i = 0, tmp; i < n; ++i) {tmp = 0;for(int j = 0, x; j < 10; ++j) {scanf("%d", &x);if(x == 0) tmp <<= 2;else if(x == 1) tmp <<= 2, tmp |= 1;else tmp <<= 1, tmp |= 1, tmp <<= 1;}++ ar[tmp];}LN = (1<<20);FWT_xor(ar, LN, 1);for (int i = 0; i < LN; ++i) ar[i] = ar[i] * ar[i] % MOD;FWT_xor(ar, LN, -1);//ar[x] 表示有多少對ai和aj異或結果為xLL ans = 0;for(int i = 0, tmp, cnt; i < LN; ++i) {tmp = i; cnt = 0;for(int j = 0, x; j < 10; ++j) {x = tmp & 3;if(x == 3) x = 1;if(x == 2) x = 4;cnt += x;tmp >>= 2;}br[cnt] = (br[cnt] + ar[i]) % MOD;}for(int i = 0; i <= 40; ++i) {ans = (ans + br[i]*br[i]%MOD)%MOD;}printf("%lld\n", ans);return 0; }

轉載于:https://www.cnblogs.com/Cwolf9/p/10348914.html

總結

以上是生活随笔為你收集整理的2019 wannafly winter camp day5-8代码库的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。