My dynamic programming questionnaire

~~Damn dynamic planning, every test basically can not write, so specially organized a dynamic planning bill of lading~~

1.CF1620F Bipartite Array

The question is equivalent to:To divide these points into two parts, each of which is not connected by an edge, is equivalent to dividing this sequence into two ascending subsequences.

The end of both sequences must be recorded at DP, but it was found that the end of one of the sequences must have been$a[i]$ or$-a[i]$ , thereforeJust record the other one's。

$f[i][0/1][j]$ denote$a[i]$ No inverse/inverse As the end of one sequence, the end of the other sequence is$j$ feasibility
Since this state value is merely infeasible and the third dimension is large, consider recording the state in the third dimension:
$f[i][0/1]$ represent$a[i]$ No inverse/inverse As the end of one sequence, the minimum of the end of the other sequence (obviously the smaller the end of the other sequence the better).

Just look at the end of which sequence the next number is placed at the time of transfer and keep track of the scheme.

It can be a bit of a pain in the ass to write.

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,inf=0x3f3f3f3f;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,a[N],f[N][2],ans[N][2];
bool check(int i,int op){
	if(f[i][op]==inf) return false;
	if(i==1) return true;
	return check(i-1,ans[i][op]);
}
void print(int i,int op){
	if(i!=1) print(i-1,ans[i][op]);
	if(op==0) printf("%d ",a[i]);
	else printf("%d ",-a[i]);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=n;i++) f[i][0]=f[i][1]=inf;
		f[1][0]=f[1][1]=-inf;
		for(int i=2;i<=n;i++){
			//divert or distract (attention etc)f[i][0]
			if(a[i]>a[i-1]&&f[i-1][0]!=inf){
				if(f[i-1][0]<f[i][0]){
					f[i][0]=min(f[i][0],f[i-1][0]);
					ans[i][0]=0;
				}
			}
			if(a[i]>f[i-1][0]&&f[i-1][0]!=inf){
				if(a[i-1]<f[i][0]){
					f[i][0]=min(f[i][0],a[i-1]);
					ans[i][0]=0;
				}
			}
			if(a[i]>-a[i-1]&&f[i-1][1]!=inf){
				if(f[i-1][1]<f[i][0]){
					f[i][0]=min(f[i][0],f[i-1][1]);
					ans[i][0]=1;
				}
			}
			if(a[i]>f[i-1][1]&&f[i-1][1]!=inf){
				if(-a[i-1]<f[i][0]){
					f[i][0]=min(f[i][0],-a[i-1]);
					ans[i][0]=1;
				}
			}
			//divert or distract (attention etc)f[i][1]
			if(-a[i]>a[i-1]&&f[i-1][0]!=inf){
				if(f[i-1][0]<f[i][1]){
					f[i][1]=min(f[i][1],f[i-1][0]);
					ans[i][1]=0;
				}
			}
			if(-a[i]>f[i-1][0]&&f[i-1][0]!=inf){
				if(a[i-1]<f[i][1]){
					f[i][1]=min(f[i][1],a[i-1]);
					ans[i][1]=0;
				}
			}
			if(-a[i]>-a[i-1]&&f[i-1][1]!=inf){
				if(f[i-1][1]<f[i][1]){
					f[i][1]=min(f[i][1],f[i-1][1]);
					ans[i][1]=1;
				}
			}
			if(-a[i]>f[i-1][1]&&f[i-1][1]!=inf){
				if(-a[i-1]<f[i][1]){
					f[i][1]=min(f[i][1],-a[i-1]);
					ans[i][1]=1;
				}
			}
		}
		if(f[n][0]!=inf||f[n][1]!=inf){
			printf("YES\n");
			if(check(n,1)) print(n,1);
			else print(n,0);
			puts("");
		}
		else puts("NO");
	}
	return 0;
}

2.CF1616H Keep XOR Low

When you see a bitwise operation, you put it directly into the Trie.

A natural idea: to set$f[i]$ denote$i$ Number of programs within the number of trees
If the current consideration of Art.$j$ Bit:

in the event that$x$ thirteenth meeting of the Conference of the Parties to the Convention on Biological Diversity (CBD)$j$ bitwise$0$That obviously left and right subtrees can't both be selected, directly$f[i]=f[ls]+f[rs]$。
in the event that$x$ thirteenth meeting of the Conference of the Parties to the Convention on Biological Diversity (CBD)$j$ bitwise$1$, and this is where things go wrong, because while each subtree can be selected at random internally, the case of selecting two subtrees at the same time is difficult to transfer.

So be bold and set$f[u][v]$ expressed in$u$ subtree and$v$ The subtree picks a few numbers each (which can be empty) so that the number of programs that satisfy the condition between them two by two ($u$ can be equal to$v$)
Note: For$u$ maybe$v$ There is no restriction on the number of selections in the self-subtree, i.e., only the cross-subtree restriction needs to be satisfied, which can be designed this way because when the$u \ne v$ when it means$u$ maybe$v$ Points within this subtree heteroscedate up to a result that is already higher up in the bit than the$x$ small

If the current consideration of Art.$j$ Bit:

in the event that$x$ thirteenth meeting of the Conference of the Parties to the Convention on Biological Diversity (CBD)$j$ bitwise$1$:
simultaneous election$u$ The left son and$v$ of the left son is clearly certain to be satisfied, while choosing the right son identically
So it was just a matter of putting the selection$u$ The left son and$v$ The right son and the chosen$u$ and the right son of$v$ Multiply that by the number of programs for the left son of the left son of the left son.
is the multiplication principle, since there is no restriction between these two steps
in the event that$x$ thirteenth meeting of the Conference of the Parties to the Convention on Biological Diversity (CBD)$j$ bitwise$0$:
At this time, only the simultaneous selection of$u$ The left son and$v$ or both the left son of the right son of the
That's the principle of addition, because these two steps, if they happen at the same time, would result in both the selection of the$u$ The left son of the left son of the left son chose again$v$ of the right son of the
But note that there is an additional case here: the
Because we$f$ The definition of an array only considers the case of cross-boundary dissimilarity, so we can also just pick the$u$ points or only select the$v$ The point of , to be additionally

Each point will be traversed only once, so the time complexity is correct

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=150000+5,M=6e6+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,x;
int tot=1,ch[M][3],Size[M],mi[M];
void insert(int x){
	int p=1;
	for(int i=30;i>=0;i--){
		int c=(x>>i)&1;
		Size[p]++;
		if(!ch[p][c]) ch[p][c]=++tot;
		p=ch[p][c];
	}
	Size[p]++;
}
int dfs(int u,int v,int d){ //The result of this calculation can have the empty set
	if(!u) return mi[Size[v]];
	if(!v) return mi[Size[u]];
	if(u==v){
		if(d==-1) return mi[Size[u]]; //Reaching the Leaves
		int ls=ch[u][0],rs=ch[u][1];
		if(x>>d&1) return dfs(ls,rs,d-1);
		else return (dfs(ls,ls,d-1)+dfs(rs,rs,d-1)-1ll+mod)%mod; //Empty sets will be counted twice so-1
	}
	if(d==-1) return mi[Size[u]+Size[v]];
	int ls1=ch[u][0],ls2=ch[v][0],rs1=ch[u][1],rs2=ch[v][1];
	if(x>>d&1) return dfs(ls1,rs2,d-1)*dfs(rs1,ls2,d-1)%mod;
	else{
		int ans=(dfs(ls1,ls2,d-1)+dfs(rs1,rs2,d-1)-1ll+mod)%mod;
		(ans += ( mi[Size[ls1]] - 1ll + mod ) * ( mi[Size[rs1]] -1ll + mod ) )%=mod;
		(ans += ( mi[Size[ls2]] - 1ll + mod ) * ( mi[Size[rs2]] -1ll + mod ) )%=mod;
		  //To subtract the case where one of the left and right subtrees is not selected，on account of(dfs(ls1,ls2,d-1)+dfs(rs1,rs2,d-1)-1ll+mod)I've done it.
		return ans;
	}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	n=read(),x=read();
	for(int i=1;i<=n;i++) insert(read());
	mi[0]=1;
	for(int i=1;i<=n;i++) (mi[i]=mi[i-1]*2ll)%=mod;
	printf("%lld\n",(dfs(1,1,30)-1ll+mod)%mod); //Can't be an empty set
	return 0;
}

3.CF1775F Laboratory on Pluto

The graph with the smallest perimeter must be a convex graph and not a concave one, or it must not be optimal.

For a convex figure, its perimeter can be transformed by translation into the perimeter of the smallest rectangle that can contain it, e.g..

First question.
Assume that the minimum rectangular side length is$a$ , $b$ If you are not a member of the team, you will have to fulfill the requirements of the$a \times b \ge n$ (Because you have to fill it in.$n$ squares), on which to make the$a+b$ As small as possible.
Assuming that we have identified the$a\times b$value, then it is clear that$a$ , $b$ The closer.$a+b$Echizen (Primary Mathematics)
The concrete proof is$(a+b)^2=(a-b)^2+4ab$....
That's for sure.$a$ , $b$ metropolis$\sqrt{n}$ Optimal, of course, does not have to be a whole number, just make up your own.
Actually, let's say.$a<b$ , then $ a \le \sqrt{n} $,$O(n \sqrt{n} )$The enumeration can be passed, and the construction scheme can be filled with whatever you want.$n$ classifier for individual things or people, general, catch-all classifier# can immediately (do sth)
Second question.
A convex figure must be obtained by gouging out four corners of that minimal rectangle, and the gouged corners must be trapezoids

First DP to find the area of$i$ The number of programs for trapezoids, specifically.
$g[i][j]$denotes the area of$i$, a total of$j$The number of schemes for a trapezoid with columns, and we specify that the number of squares in each column of the trapezoid is monotonically non-increasing
Then either add a new column or add a square to each column:$g[i][j]=g[i-1][j-1]+g[i-j][j]$
found$sum[i]$denotes the area of$i$The number of schemes of the trapezoid of$sum[i]= \sum_{j = 1}^{i} g[i][j]$
Since the total number of squares dug out must be no larger than one side length (otherwise the rectangle could be reduced entirely), the$i,j<=\sqrt{n}$
And then for the four corners of DP.
found$f[i][j]$hollow$j$A total of$i$The number of programs for a square, then$f[i][j]=f[i-k][j-1] \times sum[k]$
Or because the total number of squares dug out must be no greater than the length of one side, the four corners must not intersect.

But for example when$n=8$time, the$2 \times 4$cap (a poem)$3 \times 3$is as minimal as the length of its sides, so here we need to$O(C)$Enumerate the lengths of the edges, the$C$Indicates the perimeter.
Be careful not to do that here.$O(n)$Enumerate the lengths of the edges, because when$u=2$There are no guarantees when it comes to$n \text{sum} \le 8 \times 10^5$

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,u,mod,g[N][N],sum[N],f[N][N]; 
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	T=read(),u=read();
	if(u==1){
		while(T--){
			n=read();
			int a=sqrt(n),b=(n%a==0)?(n/a):(n/a+1);
			printf("%d %d\n",a,b);
			for(int i=1;i<=a;i++){
				for(int j=1;j<=b;j++){
					if((i-1)*b+j<=n) putchar('#');
					else putchar('.');
				}
				puts("");
			}
		}
	}
	else{
		mod=read();
		g[0][0]=1;
		for(int i=1;i<N;i++){
			for(int j=1;j<=i;j++){
				(g[i][j]=g[i-1][j-1]+g[i-j][j])%=mod;
			}
		}
		for(int i=0;i<N;i++){
			for(int j=0;j<=i;j++){
				(sum[i]+=g[i][j])%=mod;
			}
			f[i][1]=sum[i];
		}
		for(int j=2;j<=4;j++){
			for(int i=0;i<N;i++){
				for(int k=0;k<=i;k++){
					(f[i][j]+=1ll*f[i-k][j-1]*sum[k]%mod)%=mod;
				}
			}
		}
		while(T--){
			n=read();
			int a=sqrt(n),b=(n%a==0)?(n/a):(n/a+1),c=a+b,ans=0;
			for(int i=1;i<=c;i++){
				int j=c-i;
				if(i*j>=n) (ans+=f[i*j-n][4])%=mod; 
			}
			printf("%d %d\n",c*2,ans);
		}
	}
	return 0;
}

4.AT_agc002_f [AGC002F] Leftmost Ball

Because there is a limit to the number of balls of each color, in order to avoid trouble, we choose to put all the balls of the corresponding color in each time we put a ball of a color, specifically.
found$f[i][j]$ Indicates that it's currently released$i$ White balls and$j$ Number of schemes for balls of different colors
A legal scheme must satisfy that for any prefix the number of white balls is greater than or equal to the variety of colors put, i.e.$i \ge j$
For the current state of the ball release, we find the first position where the ball has not been released (empty and non-empty positions may alternate):.

If you put a white ball in it, then move it to$f[i+1][j]$
Note that when putting in the white ball we don't put in the color categories$j+1$
If you choose to put a ball that is not white (this is when you need to satisfy the$i>j$)
We already did.$j$ Species, Remaining$n-j$ The balls of each color that can be placed, excluding the white ball and the ball that must be placed in this position, are left over.$k-2$ The remaining $ n \times k - i - j \times (k-1) - 1$ positions have to be selected.$k-2$ classifier for individual things or people, general, catch-all classifier
failing agreement$f[i][j] \times (n-j) \times C_{n \times k - i - j \times (k-1) - 1}^{k-2}$ switch to$f[i][j+1]$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5,mod=1e9+7,M=4e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,k,f[N][N];
int fac[M],inv[M],q[M];
int C(int n,int m){
	return fac[n]*q[m]%mod*q[n-m]%mod;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	n=read(),k=read();
	fac[0]=1;
	for(int i=1;i<M;i++) fac[i]=fac[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<M;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	q[0]=1;
	for(int i=1;i<M;i++)
		q[i]=q[i-1]*inv[i]%mod;
	f[1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			(f[i+1][j]+=f[i][j])%=mod;
			if(i>j) (f[i][j+1]+=f[i][j]*(n-j)%mod*C(n*k-i-j*(k-1)-1,k-2)%mod)%=mod;
		}
	}
	if(k==1) printf("%lld\n",f[n][0]); //special verdictk=1
	else printf("%lld\n",f[n][n]);
	return 0;
}

5.CF1615F LEGOndary Grandmaster

Consider first how to calculate the distance between two 01 strings
A transformation: invert the numbers in all even digits of the original string such that $ \text{invert the same and neighboring numbers in the two original strings} = \text{exchange the neighboring numbers in the two new strings} $
For example, the original string from001101change into000001，
Then the new string will start with011000 -> 010100
And if two neighboring numbers in the original string are different, then they are the same in the new string, and swapping them is the same as not swapping them

So the problem is transformed into:Given two 01 strings$S$,$T$ to minimize the number of exchanges so that the first string becomes the second.
Clearly the sufficient condition for there to be a solution is$S,T$center$1$the same number of
found$a_i$indicate$S[1,i]$center$1$Number of persons, number of$b_i$indicate$T[1,i]$center$1$The answer is$\sum_{i=1}^{n} |ai-bi|$
Proof.
1. First prove that this is a lower bound, since the final state is $ \sum_{i=1}^{n} |ai-bi| =0 $ every exchange$i$ respond in singing$i+1$ It only affects$a$ center$a_i$ The value of and$|ai-bi|$ has a value of at most$-1$ , so the answer is at least$\sum_{i=1}^{n} |ai-bi|$
2. Feasibility.$|ai-bi|$Actually the calculation is the final crossing of the$i$dividing line for the exchange of$1$ordinal number
${\color{red} {this conclusion is important}}$

And then there's another set-up: theContributions are calculated separately for each position
present .$S,T$It's in the title$S,T$That is to say, there is?horn (wind instrument)
found$f[i][j]$denote that$a_i-b_i=j$the number of programs.$g[i][j]$denotes that makes $s[i,n] in the$1$ the number of 1's in t[i,n] - the number of 1's in t[i,n] = j$Number of programs of this transfer$O(n^2)$Obviously So $ans=\sum_{i=1}^{n} \sum_{j=-n}^{n}f[i][j] \times g[i+1][-j] \times |j|$
Because to fulfill the$S,T$ center$1$ lit. same number of individuals
Because subscripts cannot be negative, the offset

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n;
string s,t;
int a[N],b[N];
int f[N][N<<1],g[N][N<<1];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	T=read();
	while(T--){
		n=read();
		cin>>s>>t;
		for(int i=1;i<n;i+=2){
			if(s[i]=='0') s[i]='1';
			else if(s[i]=='1') s[i]='0';
			if(t[i]=='0') t[i]='1';
			else if(t[i]=='1') t[i]='0';
		}
		s=' '+s,t=' '+t;
		for(int i=1;i<=n;i++){
			if(s[i]!='?') a[i]=s[i]-'0';
			if(t[i]!='?') b[i]=t[i]-'0';	
		} 
		for(int i=0;i<=n+1;i++){
			for(int j=0;j<=2*n+2;j++){
				f[i][j]=g[i][j]=0;
			}
		}
		f[0][n]=1;
		for(int i=1;i<=n;i++){
			for(int j=-i;j<=i;j++){
				if(s[i]!='?'&&t[i]!='?') f[i][j+n] = f[i-1][j - (a[i]-b[i]) + n];
				else if(s[i]!='?'&&t[i]=='?') f[i][j+n] = ( f[i-1][j - (a[i]-0) + n] + f[i-1][j - (a[i]-1) + n])%mod;
				else if(s[i]=='?'&&t[i]!='?') f[i][j+n] = ( f[i-1][j - (0-b[i]) + n] + f[i-1][j - (1-b[i]) + n])%mod;
				else f[i][j+n] = ( ( f[i-1][j-1+n] + 2*f[i-1][j+n] ) % mod + f[i-1][j+1+n] )%mod;
			}
		}
		g[n+1][n]=1;
		for(int i=n;i>=1;i--){
			for(int j=-(n-i+1);j<=n-i+1;j++){
				if(s[i]!='?'&&t[i]!='?') g[i][j+n] = g[i+1][j - (a[i]-b[i]) + n];
				else if(s[i]!='?'&&t[i]=='?') g[i][j+n] = ( g[i+1][j - (a[i]-0) + n] + g[i+1][j - (a[i]-1) + n])%mod;
				else if(s[i]=='?'&&t[i]!='?') g[i][j+n] = ( g[i+1][j - (0-b[i]) + n] + g[i+1][j - (1-b[i]) + n])%mod;
				else g[i][j+n] = ( ( g[i+1][j-1+n] + 2*g[i+1][j+n] ) % mod + g[i+1][j+1+n] )%mod;
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=-n;j<=n;j++){
				(ans+=f[i][j+n]*g[i+1][-j+n]%mod*abs(j))%=mod;
			} 
		}
		printf("%lld\n",ans);
	}
	return 0;
}

6.CF1430G Yet Another DAG Problem

on account of$B_i>0$ So each side$u \to v$, $u$ The weights are greater than$v$ weights
Consider a graph layered with points in each layer having the same weights, with points in larger layers having smaller point weights, and the difference in the weights of neighboring layers must be$1$ So.$u$ The number of layers must be higher than the number of$v$ few

Consider the state-pressure DP , and suppose we now put the set of points$S$ Having placed the first several layers, we now consider the next layer, assuming that the set of points to be placed in the next layer is$T$,$T$Needs to be met.

$T \operatorname{and} S=0$, i.e.$T$ together with$S$ No intersections, equivalent to$T$ be$S$ subset of complementary set (math.)
Any one of these in$T$ hit the nail on the head$v$All that points to him.$u$ They all have to be.$S$ (With this restriction it is also necessary to satisfy all$v$ None of the points are there.$S$ center)

Consider the cost of transferring.
For everyone in the$S$ hit the nail on the head$u$ if$u \to v$ (used form a nominal expression)$v$ (euphemism) pass away$S$ In the middle, this edge produces the contribution
suppose that...$u$ at the 16th meeting$x$ Layer.$v$ at the 16th meeting$y$ layer, then the contribution of this edge should be$w_i \times (y-x)$
But that's not a very good statistic, so let's considersplit contribution:
on account of$v$ At least on the next level, so each time we transfer we add the contribution to.
$\sum w_i$
i.e., all cases that satisfy$u$ be part of$S$ , $v$ not belong to$S$ borderline$(u,v)$ neighbouring right
In that case if, at the next transfer, this edge of the$v$ remains unincorporated, then this side produces another$w_i$ contributions until$v$ is added, at which point it just happens to produce$w_i \times (y-x)$ enhancement
We preprocess each S out of.

$\sum wi \text{ (u,v) satisfies u belongs to S,v does not belong to S}$
All pointers to$S$ The point set of the points in
preprocessing complexity$O(n \times n \times 2^n)$, DP enumeration$T$ time complexity$O(3^n)$

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=(1<<18)+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m;
int tot,head[N],to[N],val[N],Next[N];
void add(int u,int v,int w){
	to[++tot]=v,Next[tot]=head[u],val[tot]=w,head[u]=tot;
}
vector<int> G[N];
int sum[M],ru[M],f[M],from[M],ans[N];
void solve(int s,int val){
	int tmp=s^from[s];
	for(int u=1;u<=n;u++)
		if((s>>(u-1))&1) ans[u]=val;
	if(from[s]) solve(from[s],val+1);
}
void print(int s){
	for(int i=1;i<=n;i++){
		if(s>>(i-1)&1) cout<<i<<' ';
	}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w);
		G[v].push_back(u); //Record the incoming edge
	}
	for(int s=0;s<(1<<n);s++){
		for(int u=1;u<=n;u++){
			if((s>>(u-1))&1){
				for(int i=head[u];i;i=Next[i]){
					int v=to[i],w=val[i];
					if(!((s>>(v-1))&1)) sum[s]+=w;
				}
				for(int v:G[u]){
					ru[s]|=(1<<(v-1));
				}
			}
		}
	}
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int s=0;s<(1<<n);s++){
		int S=s^((1<<n)-1); //compute the complement of a set
		for(int t=S;t;t=(t-1)&S){ //enumerationt
			if((ru[t]&s)==ru[t]){ //Any one of these inThit the nail on the headv,Everything that points to him.uThey all have to be.SLi (surname)
				if(f[s]+sum[s]<f[t|s])
					f[t|s]=f[s]+sum[s],from[t|s]=s;
			}
		}
	}
	solve((1<<n)-1,0);
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	puts("");
	return 0;
}

7.CF1648D Serious Business

expense or outlay$pre_{1/2/3}$Record the prefix of each line and the
found$f[x]$ denote$(1,1)$ until (a time)$(2,x)$ the best value for money.
imitate$ans=\max(f[x]+pre_3[n]-pre_3[x-1])$

Consider each operation$(l_i,r_i,k_i)$ treat (sb a certain way)$f[x]$ enhancement
Obviously for every$l_i \le y \le x$ I can all go by the following path.$(1,1) \to (1,y) \to (2,y) \to (2,x)$
assume (office)

\[f[x]=max({pre_1[y]+pre_2[x]-pre_2[y-1]-k_i})=max({pre_1[y]-pre_2[y-1]-k_i})+pre_2[x] \]

For each$l_i-1 \le y \le x$ I can also follow the path of.
$(1,1) \to (2,y) \to (2,x)$
assume (office)

\[f[x]=max({f[y]+pre_2[x]-pre_2[y]-k_i})=max({f[y]-pre_2[y]-k_i})+pre_2[x] \]

Note: Here$a[2][y]$ exist$f[y]$ It's been counted in, so it's$pre_2[y]$ No.$pre_2[y-1]$

For the second transfer it could also be streamlined.
in the event that$l_i \le y \le x$ , the path must be.
$(1,1) \to (1,z) \to (2,z) \to (2,y) \to (2,x)$
included among these$1 \le z \le y$

in the event that$li \le z \le y$"This path
$(1,1) -> (1,z) -> (2,z) -> (2,x)$
Already transferred in transfer 1
in the event that$z<l_i$This path is further subdivided into.
$(1,1) \to (1,z) \to (2,z) \to (2,l_i-1) \to (2,x)$
And this is actually$f[l_i-1]+pre_2[x]-pre_2[l_i-1-1]-k_i$

So transfer two is really just a matter of putting$f[x]$ cap (a poem)$f[l_i-1]+pre_2[x]-pre_2[l_i-1]-k_i$ get$max$

Summarizing, the transfer equation is obtained as

\[ f[x]=\max( f[l_i-1] - pre2[l_i-1] - k_i , \max({pre_1[y] - pre_2[y-1] - k_i}) ) + pre_2[x] (l_i \le y \le x) \]

Obviously it is possible to transfer the second half first and then the first half, and the transfer of the first half can be taken directly from the line tree interval$max$

Now for the second half of the transfer
The second half of the transfer needs to satisfy$l_i \le y \le x \le r_i$ I don't like it. I'm trying to get rid of one.$r_i$
Can be enumerated from back to front$x$ , and keep adding intervals so that it satisfies the$r_ i$ conditions (but not necessarily satisfying$l_i$ )
Three values are maintained on the line segment tree$max_A$ , $max_B$ , $max_{(A+B)}$

$max_A$: denotes the maximum on the corresponding interval$-k_i$
$max_B$: denotes the maximum on the corresponding interval$pre_1[y] - pre_2[y-1]$
$max_{(A+B)}$: denotes the maximum on the corresponding interval that satisfies the$-k_i + pre_1[y] - pre_2[y-1]$ (and need to meet$-k_i$ corresponding$l_i$ exist$pre_1[y] - pre_2[y-1]$ corresponding$y$ before)

So as long as the interval$[1,x]$ look sth up$max_{(A+B)}$can immediately (do sth)

insofar as$-k_i$ It can be inserted while sweeping forward, for$pre_1[y] - pre_2[y-1]$ It can be inserted in advance.
Line segment trees are merged first when they are merged$max_A$ cap (a poem)$max_B$
with regards to$max_{(A+B)}$ :: Inherit first the right and left sons$max_{(A+B)}$and add the left son's {max_A} to the right son's {max_B}.

Each of the two parts of the transfer requires a line tree

${\color{green} {interjection, really hard to write}}$

code

#include<bits/stdc++.h>
#define int long long
#define PIII pair<pair<int,int>,int>
#define fi first
#define se second
using namespace std;
const int N=5e5+5,inf=0x3f3f3f3f3f3f3f3f;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,q,a[5][N],pre[5][N],f[N];
struct P{
	int l,r,k;
}b[N];
struct node1{
	int l,r,max_A,max_B,max_sum;
};
struct SegmentTree1{
	node1 t[N<<2];
	void pushup(int p){
		t[p].max_A=max(t[p<<1].max_A,t[p<<1|1].max_A);
		t[p].max_B=max(t[p<<1].max_B,t[p<<1|1].max_B);
		t[p].max_sum=max({t[p<<1].max_sum,t[p<<1|1].max_sum,t[p<<1].max_A+t[p<<1|1].max_B});
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		if(l==r){
			t[p].max_A=t[p].max_B=t[p].max_sum=-inf;
			return;
		}
		int mid=(t[p].l+t[p].r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		pushup(p);
	}
	void change_A(int p,int x,int val){
		if(t[p].l==t[p].r){
			t[p].max_A=max(t[p].max_A,val);
			t[p].max_sum=max(t[p].max_sum,t[p].max_A+t[p].max_B);
			return;
		}
		int mid=(t[p].l+t[p].r)>>1;
		if(x<=mid) change_A(p<<1,x,val);
		else change_A(p<<1|1,x,val);
		pushup(p);
	}
	void change_B(int p,int x,int val){
		if(t[p].l==t[p].r){
			t[p].max_B=max(t[p].max_B,val);
			t[p].max_sum=max(t[p].max_sum,t[p].max_A+t[p].max_B);
			return;
		}
		int mid=(t[p].l+t[p].r)>>1;
		if(x<=mid) change_B(p<<1,x,val);
		else change_B(p<<1|1,x,val);
		pushup(p);
	}
	PIII ask(int p,int l,int r){
		if(l<=t[p].l&&t[p].r<=r) return {{t[p].max_A,t[p].max_B},t[p].max_sum};
		int mid=(t[p].l+t[p].r)>>1;
		if(r<=mid) return ask(p<<1,l,r);
		if(l>mid) return ask(p<<1|1,l,r);
		PIII res1=ask(p<<1,l,r),res2=ask(p<<1|1,l,r);
		int max_A=max(,),max_B=max(,),max_sum=max({,,+});
		return {{max_A,max_B},max_sum};
	}
}T1;
struct node2{
	int l,r,maxn,lazy;
	void tag(int val){
		maxn=max(maxn,val);
		lazy=max(lazy,val);
	}
};
struct SegmentTree2{
	node2 t[N<<2];
	void pushup(int p){
		t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
	}
	void spread(int p){
		if(t[p].lazy!=-inf){
			t[p<<1].tag(t[p].lazy);
			t[p<<1|1].tag(t[p].lazy);
			t[p].lazy=-inf;
		}
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r,t[p].lazy=-inf;
		if(l==r){
			t[p].maxn=f[l];
			return;
		}
		int mid=(t[p].l+t[p].r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		pushup(p);
	}
	void change(int p,int l,int r,int val){
		if(l<=t[p].l&&t[p].r<=r){
			t[p].tag(val);
			return;
		}
		spread(p);
		int mid=(t[p].l+t[p].r)>>1;
		if(l<=mid) change(p<<1,l,r,val);
		if(r>mid) change(p<<1|1,l,r,val);
		pushup(p);
	}
	int ask(int p,int x){
		if(t[p].l==t[p].r) return t[p].maxn;
		spread(p);
		int mid=(t[p].l+t[p].r)>>1;
		if(x<=mid) return ask(p<<1,x);
		else return ask(p<<1|1,x);
	}
}T2;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=3;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=read();
			pre[i][j]=pre[i][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=q;i++) b[i].l=read(),b[i].r=read(),b[i].k=read();
	
	(1,1,n);
	for(int i=1;i<=n;i++)
		T1.change_B(1,i,pre[1][i] - pre[2][i-1]);
	sort(b+1,b+q+1,[](const P&x,const P&y){return >;});
	int i=1;
	for(int x=n;x>=1;x--){
		while(i<=q&&b[i].r>=x) T1.change_A(1,b[i].l,-b[i].k),i++;
		f[x]=(1,1,x).se; //Don't add it yet.pre[2][x]
	}
	
	(1,1,n); //Build the tree by directly following thefarrays
	
	sort(b+1,b+q+1,[](const P&x,const P&y){return <;});
	for(int i=1;i<=q;i++){
		int l=b[i].l,r=b[i].r;
		if(l>1){
			int tmp=(1,l-1);
			(1,l,r,tmp-b[i].k);
			//Note that this time because our end point is not(2,l-1),f[l-1]So you can't addpre[2][l-1],Directly with the original unaddedpre2(used form a nominal expression)f值是对(used form a nominal expression)
		}
		//这个转移(used form a nominal expression)意义是先走到(2,l-1),the reason whyl!=1
	}
	for(int i=1;i<=n;i++) f[i]=(1,i)+pre[2][i];
	int ans=-inf;
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i]+pre[3][n]-pre[3][i-1]);
	}
	printf("%lld\n",ans);
	return 0;
}

8.CF367E Sereja and Intervals

A conclusion about mutually exclusive intervals:
If the left endpoints of the interval are sorted in ascending order, the right endpoints of the interval must also be sorted in ascending order
That means that when you confirm the$n$ classifier for individual things or people, general, catch-all classifier$l_i$ , and$n$ classifier for individual things or people, general, catch-all classifier$r_i$Then their method of combination is unique.
So now you have to construct two sequences {$l_i$},{$r_i$}, meet:

$1 \le l_1 < l_2 < l_3 < l_4 < l_5 < ...< l_n \le m$
$ 1 \le r_1 < r_2 < r_3 < r_4 < r_5 < ... < r_n<=m $
$l_i \le r_i$
$\text{exist} l_i=x$

Consider a few properties.

It is impossible to have a point with two left endpoints/right endpoints
$n>m$ when there is no solution, so it can be assumed that$n \le m$ , i.e.$n \le \sqrt {10^5}$
The 3 restriction is equivalent to the fact that for every$i$, the left endpoint of its left$cnt(l,i)$ numbers of$\ge$ The number of right endpoints to its left$cnt(r,i)$

If there is no limit 4, consider DP.
$f[i][j][k]$ preface$i$ Position allocation$j$ classifier for individual things or people, general, catch-all classifier$l$ Endpoints$k$ classifier for individual things or people, general, catch-all classifier$r$ Number of programs at endpoints$(j \ge k)$ 。
When transferring, for each position you either assign a$l$ , either by assigning a$r$ Either the distribution of$l$ , $r$ One each, or nothing at all.
time complexity$O(m \times n^2)$

If there is a restriction4 , it is really only necessary to add a new line in the$i=x$ whenForced transfer of only cases with put left endpoints

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,x;
int f[2][400][400]; //rolling array
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	n=read(),m=read(),x=read();
	if(n>m){
		printf("0\n");
		return 0;
	}
	f[0][0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=min(i,n);j++){
			for(int k=0;k<=j;k++){
				if(j-1>=k&&j-1>=0) (f[i&1][j][k]+=f[1-(i&1)][j-1][k])%=mod;
				if(i!=x&&k-1>=0) (f[i&1][j][k]+=f[1-(i&1)][j][k-1])%=mod;
				if(j-1>=0&&k-1>=0) (f[i&1][j][k]+=f[1-(i&1)][j-1][k-1])%=mod;
				if(i!=x) (f[i&1][j][k]+=f[1-(i&1)][j][k])%=mod;
			}
		}
		for(int j=0;j<=min(n,i);j++){
			for(int k=0;k<=j;k++){
				f[1-(i&1)][j][k]=0;
			}
		}
	}
	int fac=1;
	for(int i=1;i<=n;i++) (fac*=i)%=mod; //The intervals are numbered so multiply byn!
	printf("%lld\n",f[m&1][n][n]*fac%mod);
	return 0;
}

9.CF1574F Occurrences

This restriction is really abstract, and the subsequence in this question refers to the substring, to avoid misunderstanding the following directly write substring

Consider transformation constraints.
If you think about it you can realize that$A$ in sequence$a$ For every occurrence in the
Each of its substrings occurs once, and the one with the most occurrences must be of length$1$of a single character.
So the limit is really.$A$ exist$a$ Number of occurrences in$=$ Each of its characters in the$a$ The number of occurrences in the

Consider several scenarios.

in the event that$A=\text{123}$, at which point when$a$ Fill in a1 When you fill in the form, be sure to follow the instructions.2,3assume (office)$a$ Either there is no1 If there is, it must be in the form of123 of the form in which it appeared.
If you connect the edges you will find that at this point$1 \to 2 \to 3$Form a chain.
in the event that$A=\text{121}$You'll find that at this point, no matter how you fill in the1The number of occurrences must be greater than$A$unless not filled in1。
And at this point the connecting edges will have rings, i.e. those with rings must not be filled.
in the event that$A=\text{123},B=\text{234}$At this point, it's time to put$A$ cap (a poem)$B$ The chains are merged into1234。
in the event that$A=\text{123},B=\text{124}$, at which point there is a branch, which again cannot be filled in.

And so a practice took shape: the

At the beginning each number forms itself into a connected block.
For each sequence$A$ , connecting the edges in order.
For every connected block, if it has a ring or if it has a branch (i.e., it is not a chain), then no number within that connected block can appear in the$a$ Center.
Otherwise this chain can appear in a
Do a complete backpack for each chain that can occur, i.e., if the length is$j$ The chain of$w_j$ Individuals.$f[i]$ means that the construction length is$i$ (used form a nominal expression)$a$ The number of programs with$f[i]=\sum_{j=1}^i f[i-j] \times w_j$

Shifting in this way can speed things up considerably, since enumerating each chain may have$O(k)$individuals, but the different chain lengths must be less than or equal to the$O(\sqrt {k})$classifier for individual things or people, general, catch-all classifier
Since it is assumed that different chain lengths have$l$ individuals, then even if the length of these chains is$1,2,3,4,...,l$
imitate$(1+2+3+..+l)=\frac {(1+l) \times l}{2} \le k$, i.e. $ l \le \sqrt{2k}$

code

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=3e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,k,a[N]; 
map<PII,bool> mp;
int tot,head[N],to[N],Next[N],ru[N],chu[N]; 
void add(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
	ru[v]++,chu[u]++;
}
int num,c[N],siz[N];
bool vis[N],flag[N];
void dfs(int u){
	siz[num]++;
	vis[u]=true,c[u]=num;
	for(int i=head[u];i;i=Next[i]){
		int v=to[i];
		if(vis[v]) flag[num]=false;
		else dfs(v);
	}
}
set<int> len;
int w[N],f[N];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),k=read();
	memset(flag,true,sizeof flag);
	for(int i=1;i<=n;i++){
		int c=read(),lst;
		for(int j=1;j<=c;j++){
			a[j]=read();
			if(j>1&&!mp[{lst,a[j]}]) add(lst,a[j]),mp[{lst,a[j]}]=true;;
			lst=a[j];
		}
	}
	for(int i=1;i<=k;i++){
		if(!vis[i]&&ru[i]==0) num++,dfs(i);
	}
	for(int i=1;i<=k;i++) 
		if(ru[i]>1||chu[i]>1) flag[c[i]]=false;
	for(int i=1;i<=num;i++)
		if(flag[i]) (siz[i]),w[siz[i]]++;

	f[0]=1;
	
	for(int i=1;i<=m;i++){
		for(int x:len) if(i>=x) (f[i]+=f[i-x]*w[x])%=mod;
	}
	printf("%lld\n",f[m]);
	return 0;
}

10.P5662 [CSP-J2019] Memorabilia

This is because souvenirs purchased on the same day can also be sold for gold coins on the same day.
So if one wants to keep a memento one can look at it as.

Buy on day one, sell the next morning, buy back the next day, sell the third morning, buy back the third day...

This way I don't have to worry about how many souvenirs I have on hand each day, I just have to assume that what I buy that day will be sold early the next morning and nothing will be left, and whether I buy it again or not is the next day's business .

found$A_{i,j}$ denote$i$ sky$j$ The price of the item.
Suppose I take into account the first$i$ Days left in hand$M$ For one item, it will cost you$A_{i,j}$ dollars, the gain is$A_{i+1,j} - A_{i,j}$。
can be viewed as having a volume of$M$ of the backpack, the volume of each item is$A_{i,j}$ The value is$A_{i+1,j} - A_{i,j}$ The Complete Backpack
Finally, you can use the maximum value obtained on that day as the starting capital for the next day.

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,M,a[105][105];
int f[N];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
	T=read(),n=read(),M=read();
	for(int i=1;i<=T;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=read();
		}
	}
	for(int i=1;i<T;i++){
		for(int k=0;k<=M;k++) f[k]=0;
		for(int j=1;j<=n;j++){
			for(int k=a[i][j];k<=M;k++){
				f[k]=max(f[k],f[k-a[i][j]]+a[i+1][j]-a[i][j]);
			}
		}
		M=M+f[M]; //on account offThe array counts how much can be gained，the reason whyMindirectly+f[M]
	}
	printf("%d\n",M);
	return 0;
}

11.P2886 [USACO07NOV] Cow Relays G

Matrix Fast Power Optimization DP Board

We use a matrix to represent the answers between two by two, at first$A[i][j]$ indicate$i$ , $j$ The shortest circuit that passes through only one edge
Change the matrix multiplication to$C[i][j] = min(A[i][k]+A[k][j])$
Here k is equivalent to enumerating the transit points (cf. Floyd)
And at this point, the path length will become two times, the final requirement is n times, do the matrix fast power can be

code

#include<bits/stdc++.h>
#define int long long
#define PIII pair<int,pair<int,int> >
#define fi first
#define se second
using namespace std;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int dis[10005],N,n,m,s,t;
vector<PIII> G;
int Dis(int x){
	return lower_bound(dis+1,dis+n+1,x)-dis;
}

int ans[1005][1005],c[1005][1005];
void mul(int f[1005][1005],int a[1005][1005]){ //matrix multiplication
	memset(c,0x3f,sizeof c);
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				c[i][j]=min(c[i][j],f[i][k]+a[k][j]);
			}
		}
	}
	memcpy(f,c,sizeof c);
}
void Quick_power(int a[1005][1005],int b){
	for(int i=1;i<=n;i++){ //unit matrix
		for(int j=1;j<=n;j++){
			if(i==j) ans[i][j]=0;
			else ans[i][j]=0x3f3f3f3f3f3f3f3f;
		}
	}
	while(b){
		if(b&1) mul(ans,a);
		b>>=1,mul(a,a);
	}
	memcpy(a,ans,sizeof ans);
}
int a[1005][1005];
signed main(){
	N=read(),m=read(),s=read(),t=read();
	memset(a,0x3f,sizeof a);
	for(int i=1;i<=m;i++){
		int w=read(),u=read(),v=read();
		G.push_back({u,{v,w}});
		dis[i]=u,dis[i+m]=v;
	}
	sort(dis+1,dis+2*m+1);
	n=unique(dis+1,dis+2*m+1)-dis-1;
	for(PIII x:G){
		int u=,v=,w=;
		u=Dis(u),v=Dis(v);
		a[u][v]=a[v][u]=w;
	}
	
	Quick_power(a,N);
	
	printf("%lld\n",a[Dis(s)][Dis(t)]);
	return 0;
}

12.P6569 [NOI Online #3 Raise Group] Magic Value

The same transfer case comes to mind again for matrix fast powers.

Constructing the transfer matrix$G$ , if$u$,$v$ There is an edge between , then$G[u][v]=1$ Otherwise.$G[u][v]=0$
Change the matrix multiplication to$C[i][j] = \operatorname{xor} ^ n _ {k=1} A[i][k] \times B[k][j]$
Note:Generalized moment multiplication must satisfy the law of union if it is to satisfy the law of union - addition satisfies the law of exchange, multiplication satisfies the law of union, and satisfies the distributive rate for addition, whereas ordinary dissimilarity or addition does not have a distributive law and cannot be altered in this way, but since here there are only$0/1$ So it's okay.

The total time complexity of direct fast powers is $ O(q \times n^3 * \log a)$ over.
So consider preprocessing out$G^1,G^2,G^4,......$ , and to the$a$ Perform binary splittingThis way each multiplication is a$n \times n$Matrix multiplied by$1 \times n$vector, the time complexity becomes $ O(q \times n^2 * \log a)$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,q; 
struct matrix{
	int x[105][105];
	int n,m;
}f,a,mi[40];
matrix mul(matrix x,matrix y){
	matrix ans;
	=,=;
	memset(,0,sizeof );
	for(int k=1;k<=;k++){
		for(int i=1;i<=;i++){
			for(int j=1;j<=;j++){
				[i][j]^=([i][k]*[k][j]);
			}
		}
	}
	
	return ans;
}
signed main(){
	n=read(),m=read(),q=read();
	=1,=n;
	=n,=n;
	for(int i=1;i<=n;i++) [1][i]=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		[u][v]=[v][u]=1;
	}
	
	mi[0]=a;
	for(int i=1;i<=32;i++) mi[i]=mul(mi[i-1],mi[i-1]);
	
	
	while(q--){
		int t=read();
		matrix ans=f;
		for(int i=0;i<=32;i++){
			if(t>>i&1) ans=mul(ans,mi[i]);
		}
		printf("%lld\n",[1][1]);
	}
	return 0;
}

13.P6190 [NOI Online #1 Starter Group] Magic

A legitimate$1 \to n$ The path can be split into two parts: the

There's no path to magic at first
A number of segments satisfy:the first path used with magic, followed by unused paths

And if you can use it all up you'll be sure to put$k$ Sub-magic runs out.
the reason why$A[i][j]$ indicate$i$ until (a time)$j$ Use magic once and at the shortest distance of the first bar.
Matrix fast powers to$A^k$ That is, it's used$k$ Sub-Magic.
Note that you also have to run an all-source shortest circuit with Floyd to deal with the minima of paths that don't have any magic in them.

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1e15;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,k;
void Init(int a[105][105]){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j) a[i][j]=inf; //Special judgment here. i!=j , take precautions 1--n Possible shortfalls in pathways k The case of the strip edge
		}
	}
}
int ans[105][105],c[105][105];
void mul(int f[105][105],int a[105][105]){ //matrix multiplication
	Init(c);
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				c[i][j]=min(c[i][j],f[i][k]+a[k][j]);
			}
		}
	}
	memcpy(f,c,sizeof c);
}
void Quick_power(int a[105][105],int b){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) ans[i][j]=0;
			else ans[i][j]=inf;
		}
	}
	while(b){
		if(b&1) mul(ans,a);
		b>>=1,mul(a,a);
	}
	memcpy(a,ans,sizeof ans);
}

int f[105][105],a[105][105];
int tot,head[N],to[N],Next[N],val[N];
void add(int u,int v,int w){
	to[++tot]=v,Next[tot]=head[u],val[tot]=w,head[u]=tot;
}
signed main(){
	n=read(),m=read(),k=read();
	
	Init(f);
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		f[u][v]=w;
		add(u,v,w);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				
			}
		}
	}
	
	if(k==0){
		printf("%lld\n",f[1][n]);
		return 0;
	}
	
	Init(a);
	for(int u=1;u<=n;u++){
		for(int v=1;v<=n;v++){
			for(int i=head[u];i;i=Next[i]){
				int w=val[i];
				a[u][v]=min(a[u][v],-w+f[to[i]][v]);
			}
		}
	}
	
	Quick_power(a,k);

	int res=inf;
	for(int u=1;u<=n;u++){
		res=min(res,f[1][u]+a[u][n]);
	}
	printf("%lld\n",res);
	return 0;
}

14.P6772 [NOI2020] Gourmet Foodie

Plain DP.$f[i][u]$ denote$i$ Good day.$u$ The maximum benefit of the
imitate$f[i][u] = max(f[i-w][v]+c[u])$ (There exists an edge$(v,u,w)$ )

on account of$T$ is very large, consider matrix fast power optimization:
due toMatrix fast powers can generally only be optimized from$f[i] \to f[i+1]$ transfersSo considercrunch points。
Tip:The reason why we don't split the edges is because n is small.
i.e., putting a point$u$ Split it into $ u_1,u_2,u_3,u_4,u_5$.
in accordance with$u_1 \to u_2 \to u_3 \to u_4 \to u_5$ plurilateral
If there exists an edge$(u,v,3)$ follow$u_3 -> v_1$ plurilateral
The equivalent of how many edges have passed in the new graph is a few days.
and only at the first point where all nodes split, i.e., the$u_1$ on $c[ u_1 ] = c[u] $, the rest of the points of the$c$ The values are all$0$。

Design Transfer Matrix$G$ If the new chart$u$ respond in singing$v$ with edges between them.
imitate$G[u][v] = c[v]$or else$G[u][v] = -inf$ 。
Changing the definition of moment multiplication.
$ C[i][j] = \max{A[i][k] + B[k][j]} $。

In the beginning, in addition to$f[1][1]=c[1]$ The rest are$-inf$。
If food festivals are not considered, then answer$=Ans[1][1]$ which$Ans=f \times G^T$

For cases where there are food festivals.
Do a Plain Shift at Every Food FestivalSpecifically.
Because each food festival is not held one at a time, firstSort by time of day for each food festival。
with regards to$t[i-1]$ until (a time)$t[i]$ :
imitate$f = f * G ^ {t[i] - t[i-1]}$
After that, you can specialize the$f[1][x[i] ] = f[1][x[i]] + y[i]$。
eventual$t[k] \ne T$ Then the$f = f * G ^ (T-t[k])$
But the time complexity is$O(k \times (5n) ^ 3 \times \log T)$

To optimize the complexity, let's considerBinary Split OptimizationSeeP6569 [NOI Online #3 Raise Group] Magic Value
connect all$G^1,G^2,G^4 ....$ Preprocessing out, preprocessing time complexity$O((5n) ^ 3 * \log T)$。
Each binary split$t[i]-t[i-1]$ , multiply the corresponding matrices in turn.
Since every multiplication here is a$1 \times 5n$ vectors$f$ Take a ride on a$5n \times 5n$ matrices$G$ The time complexity is only$O(k * (5n) ^ 2 \times logT)$

total time complexity$O((5n) ^ 3 \times \log T + k \times (5n) ^ 2 \times \log T)$

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,inf=5e15;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,T,k;
int c[N];
struct Festival{
	int t,x,y;
}a[N];
bool edge[300][300];
void add(int u,int v){
	edge[u][v]=true;
}

struct Matrix{
	int a[300][300];
	int n,m;
	void Init(int val){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				a[i][j]=val;
			}
		}
	}
}G,F,mi[32];
Matrix operator * (const Matrix &A,const Matrix &B){
	Matrix C;
	=,=;
	(-inf); 
	for(int k=1;k<=;k++){
		for(int i=1;i<=;i++){
			for(int j=1;j<=;j++){
				[i][j]=max([i][j],[i][k]+[k][j]);
			}
		}
	}
	return C;
}
signed main(){
	n=read(),m=read(),T=read(),k=read();
	for(int i=1;i<=n;i++){
		c[i]=read();
		for(int j=1;j<=4;j++){
			add(i+(j-1)*n,i+j*n);
		}
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		add(u+(w-1)*n,v);
	}
	for(int i=1;i<=k;i++){
		a[i].t=read(),a[i].x=read(),a[i].y=read();
	}
	
	=1,=5*n;
	=5*n,=5*n;
	(-inf);
	[1][1]=c[1];
	for(int i=1;i<=5*n;i++){
		for(int j=1;j<=5*n;j++){
			if(edge[i][j]) [i][j]=c[j];
			else [i][j]=-inf;
		}
	}
	mi[0]=G;
	for(int i=1;i<=30;i++) mi[i]=mi[i-1]*mi[i-1]; 
	
	sort(a+1,a+k+1,[](Festival x,Festival y){return <;});
	a[0].t=0;
	for(int i=1;i<=k;i++){
		int t=a[i].t-a[i-1].t;
		for(int j=0;j<=30;j++)
			if(t>>j&1) F=F*mi[j];
		[1][a[i].x]+=a[i].y;
	}
	if(a[k].t!=T){
		int t=T-a[k].t;
		for(int j=0;j<=30;j++)
			if(t>>j&1) F=F*mi[j];
	}
	
	if([1][1]<0) printf("-1\n");
	else printf("%lld\n",[1][1]);
	return 0;
}

15.CF1051E Vasya and Big Integers

found$f[i]$ Indicates post-division$[i,n]$ of the program.
be able to obtain information from$f[j]$ switch to$f[i]$ (used form a nominal expression)$j$ It's got to be.$[i+lenL,i+lenR]$ A continuous interval in ($lenR$ because of$r$ The length of the$lenL$ because of$l$ length).
In fact, only$j=i+lenR$ respond in singing$j=i+LenL$ It may not be legal, so just make a special judgment (binary + hash or ex_KMP).
Transfer with suffixes and optimization.
The reason for designing the state this way is that this basically eliminates the need to consider leading zeros.

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
string s,a,b;
int n,lenL,lenR;
int z[N],p1[N],p2[N];
int f[N],q[N];
void Init(){
	int l=0,r=0;
	z[1]=lenL;
	for(int i=2;i<=lenL;i++){
		if(i<=r) z[i]=min(r-i+1,z[i-l+1]);
		while(a[1+z[i]]==a[i+z[i]]) z[i]++;
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
	l=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r) p1[i]=min(r-i+1,z[i-l+1]);
		while(1+p1[i]<=lenL&&i+p1[i]<=n&&s[i+p1[i]]==a[1+p1[i]]) p1[i]++;
		if(i+p1[i]-1>r) l=i,r=i+p1[i]-1;
	}
	
	memset(z,0,sizeof z); //empty!!!!!!
	l=0,r=0;
	z[1]=lenR;
	for(int i=2;i<=lenR;i++){
		if(i<=r) z[i]=min(r-i+1,z[i-l+1]);
		while(b[1+z[i]]==b[i+z[i]]) z[i]++;
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
	l=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r) p2[i]=min(r-i+1,z[i-l+1]);
		while(1+p2[i]<=lenR&&i+p2[i]<=n&&s[i+p2[i]]==b[1+p2[i]]) p2[i]++;
		if(i+p2[i]-1>r) l=i,r=i+p2[i]-1;
	}
}
bool cmp1(int l,int r){
	if(r-l+1<lenL) return false;
	if(r-l+1>lenL) return true;
	if(p1[l]==lenL) return true;
	return a[1+p1[l]]<=s[l+p1[l]];
}
bool cmp2(int l,int r){
	if(r-l+1<lenR) return true;
	if(r-l+1>lenR) return false;
	if(p2[l]==lenR) return true;
	return b[1+p2[l]]>=s[l+p2[l]];
}
bool check(int l,int r){
	if(l>r) return false;
	return cmp1(l,r)&&cmp2(l,r);
}
signed main(){
// freopen("","r",stdin);
// freopen("","w",stdout);
	cin>>s>>a>>b;
	n=(),lenL=(),lenR=();
	s=' '+s,a=' '+a,b=' '+b;
	Init();
	
	f[n+1]=1;
	q[n+1]=1;
	for(int i=n;i>=1;i--){
		if(s[i]=='0'){
			if(check(i,i)) f[i]=f[i+1];
		}
		else{
			int l=min(n+1,i+lenL),r=min(n+1,i+lenR);
			if(!check(i,l-1)) l++;
			if(!check(i,r-1)) r--;
			if(l<=r) f[i]=(q[l]-q[r+1]+mod)%mod;
			else f[i]=0;
		}
		q[i]=(q[i+1]+f[i])%mod;
	}
	printf("%lld\n",f[1]);
	return 0;
}

16.CF1310C Au Pont Rouge

All substrings are sorted and dichotomized into answers.
check is equivalent to asking for the$S$ split$m$ Segment sizes are all greater than the number of schemes for a given substring, and the transfer is similar to the previous question .

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,cnt,k;
string s;
int lcp[1005][1005];
struct P{
	int l,r;
}a[N];
bool operator > (P const &x, P const &y) {
	int L=lcp[][];
	if (L>=+1||L>=+1)
		return +1>+1;
	return s[+L]>s[+L];
}
int f[1005][1005],q[1005][1005];
// f[j][i] denote [i,n] divide sth. into j Make each segment larger than the given，q[j][i]express a view on j suffix and。
int check(P x){
	memset(f,0,sizeof f);
	memset(q,0,sizeof q);
	f[0][n+1]=1;
	for(int i=n+1;i>=1;i--) q[0][i]=q[0][i+1]+f[0][i];
	int l=,r=,len=r-l+1;
	for(int j=1;j<=m;j++){
		for(int i=n;i>=1;i--){
			int tmp=min(len,lcp[i][l]);
			if(tmp==len||s[i+tmp]>=s[l+tmp])
				f[j][i]=q[j-1][i+tmp+1];
		}
		for(int i=n;i>=1;i--) q[j][i]=min((long long)1e18,q[j][i+1]+f[j][i]); //Prevent it from blowing up.
	}
	return f[m][1];
}
signed main(){
	n=read(),m=read(),k=read();
	cin>>s; s=' '+s;
	lcp[n][n]=1;
	for(int i=n;i>=1;i--){
		for(int j=n;j>=1;j--){
			if(i==j&&i==n) continue;
			if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
			else lcp[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			a[++cnt]={i,j};
		}
	}
	
	sort(a+1,a+cnt+1,greater<P>());
	
	int l=1,r=cnt,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(a[mid])+1<=k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	for(int i=a[ans].l;i<=a[ans].r;i++){
		printf("%c",s[i]);
	}
	printf("\n");
	return 0;
}

17.CF477D Dreamoon and Binary

Number of programs:
A well thought out DP, set$f[i][j]$ indicates that the last paragraph is$[j,i]$ Delineation$[1,i]$ of the number of programs.
imitate$f[i][j]=\sum_{k=j-1-len+1}^{j-1} f[j-1][k]$ , where $ len=i-j+1$.
Transfers can be done with prefixes and optimizations$O(n^2)$。
pay attention to what happens when$k=j-1-len+1$ assume (office)$s[k,j-1]$ cap (a poem)$s[j,i]$ To determine whether the former is smaller than the latter when the lengths are the same, the LCP can be preprocessed.
For the lead$0$The processing only needs to be done in the$0$The position of the prefix and is not counted into the prefix sum.
Minimum number of operations:
At first glance after taking the modulus it seems that you can't compare sizes, so you can't DP ,so analyze the properties.
Consider how the final answer counts: the
$ans = \text{print count + plus one count} = m+val$。
included among these$m$ is the number of paragraphs.$val$ is the value of the last segment.
Suppose the last paragraph is$s[i,n]$。
(coll.) fail (a student)$i$ When moving forward, the$m$ It will only be reduced by a maximum of$1$ whereas$val$ would be an order of magnitude more, and the$m \le 5000 < 2^{17}$，
So we actuallyJust consider$n-16 \le i\le n$ answersThat is, if the division of this position is not legal is f[n][i]=0 in the first question.
All we need is DP to find the minimum number of segments, and here, since$j \le i$ If you record the minimum value of the suffix at DP, you can do the same.$O(n^2)$
Tip:Of course if there is no solution in this interval you have to move on. (see code)

make sb change their ways, opinions etcdefine int long long Card space

code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5,inf=0x3f3f3f3f;
const ll mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
string s;
int n;
int lcp[5005][5005];
void Init(){
	for(int i=n;i>=1;i--){
		for(int j=n;j>=1;j--){
			if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
			else lcp[i][j]=0;
		}
	}
}
bool cmp(int l,int r,int x,int y){ //judgementss[l,r]is or isn't<=s[x,y]
	int len1=r-l+1,len2=y-x+1;
	if(len1<len2) return true;
	if(len1>len2) return false;
	if(lcp[l][x]>=len1) return true;
	return s[l+lcp[l][x]]<=s[x+lcp[l][x]];
}
int f[5005][5005],q[5005][5005];
int g[5005][5005],ming[5005][5005]; //Minimum number of segments,gMinimum value of the suffix of an array
void solve1(){
	memset(g,0x3f,sizeof g);
	memset(ming,0x3f,sizeof ming);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(i!=j&&s[j]=='0'){
				f[i][j]=0;
				g[i][j]=inf;
			}
			else if(j==1){
				f[i][j]=1;
				g[i][j]=1;
			}
			else{
				int k=j-1-(i-j+1)+1; k=max(k,1);
				if(!cmp(k,j-1,j,i)) k++;
				f[i][j]=((ll)(q[j-1][j-1]+mod-q[j-1][k-1]))%mod;
				g[i][j]=ming[j-1][k]+1;
			}
			q[i][j]=((ll)(q[i][j-1]+f[i][j]))%mod;
		}
		for(int j=i;j>=1;j--) ming[i][j]=min(ming[i][j+1],g[i][j]);
	}
	printf("%d\n",q[n][n]);
}
void solve2(){
	ll mi=1,val=0,ans=inf;
	bool flag=false; //记录is or isn't出现了解，in the event that i exist [n-16,n] I don't have a solution. I'm going to move on.
	for(int i=n;i>=max(1,n-16);i--){
		val=val+(ll)(s[i]-'0')*mi; mi*=2ll;
		if(f[n][i]!=0) flag=true,ans=min(ans,(ll)(g[n][i]+val));
	}
	if(flag){
		printf("%lld\n",ans%mod);
		return;
	}
	
	for(int i=n-17;i>=1;i--){
		val=(val+(ll)(s[i]-'0')*mi)%mod; (mi*=2ll)%=mod;
		if(f[n][i]!=0){
			printf("%lld\n",(ll)(g[n][i]+val)%mod);
			return;
		}
	}

}
signed main(){
	cin>>s;
	n=(); s=' '+s;
	Init();
	solve1();
	solve2();
	return 0;
}

18.CF1562E Rescue Niwen!

sol1 (human intelligence)

former$O(n^2)$ DP Find all$LCP(i,j)$。
found$f[l,r]$ expressed in terms of$[l,r]$ This substring is the end LIS , the$F[i]$ indicate$f[i,n]$。
Noting that, for the purposes of the$[l,r]$ This substring is the final LIS, and I can definitely follow it.$[l,r+1] [l,r+2], ... ,[l,n]$ ，
So the final answer must be$\max ^n_{i=1} f[i,n]$ , i.e.$\max ^n_{i=1} F[i]$。

as$LCP(i,j)=len (j<i)$ :

in the event that$s[j+len]>s[i+len]$ If it does not, it will not be able to make a contribution
in the event that$s[j+len]<s[i+len]$ imitate$F[i]=\max(F[i],F[j] + n - (i+len) +1)$ ，
That is, for people who are based on$[j,n]$ This substring is the LIS at the end and is then connected to the$[i,i+len] , [i,i+len+1] , ... ,[i,n]$ 。

time complexity$O(n^2)$

sol2 (conventional practice)

There is also a solution based on$LCP$ Sort (i.e., in dictionary order) and then discretize, assigning each string a value that represents his ranking.
Sort again according to the title and run normal$LIS$。

time complexity$O(n^2 \log n^2)$It's a matter of luck.

code(sol1)

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T;
int n,lcp[5005][5005],f[5005];
string s;
signed main(){
	T=read();
	while(T--){
		n=read();
		cin>>s; s=' '+s;
		for(int i=1;i<=n;i++){
			f[i]=0;
			for(int j=1;j<=n;j++){
				lcp[i][j]=0;
			}
		}
		lcp[n][n]=1;
		for(int i=n;i>=1;i--){
			for(int j=n;j>=1;j--){
				if(i==n&&j==n) continue;
				if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
				else lcp[i][j]=0;
			}
		}
		int ans;
		ans=n;
		for(int i=1;i<=n;i++){
			f[i]=n-i+1;
			for(int j=1;j<i;j++){
				if(s[j+lcp[i][j]] < s[i+lcp[i][j]])
					f[i]=max(f[i],f[j]+n-(i+lcp[i][j])+1);
			}
			ans=max(ans,f[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

19.CF1701E Text Editor

if nothome Operation. Obviously it doesn't work.right At this point, the answer is$n - LCP(S,T)$ ( LCP is the Longest Common Prefix).
If there ishome , the strategy at this point must be something like this.

Delete from back to front, each time you spend$1$ carry outleft maybeBackspace
florid$1$ check or refer tohome
From the top to the bottom, every time you spend$1$ check or refer toright or Spend$2$ firstlyright press againBackspace
Remaining middle section$S,T$ It's the same. You don't have to move.

Consider two DPs, front-to-back and back-to-front, and take front-to-back as an example.
$f[i][j]$ means to operate from the front to the back, and the current operation is completed with the cursor in the$i$ empresslet$S[1,i]$ cap (a poem)$T[1,j]$ The minimum cost of matching.
Transfer:

removing$f[i][j]=min(f[i][j],f[i-1][j]+2)$
Not deleted If$s[i]=t[j]$ , $f[i][j]=min(f[i][j],f[i-1][j-1]+1)$

Similarly from back to front, with$g[i][j]$ means that the current operation is completed with the cursor at$j$ aheadlet$S[i,n]$ cap (a poem)$T[j,m]$ Minimum cost of matching

But notice that we have one more section, the remaining middle section.$S,T$ is the same as not having to move, and in our transfer above, this is the section where we'll also use the move build, but it's not really necessary.
That's why it's a good idea to use$F[i][j]$ away$S[1,i]$ cap (a poem)$T[1,j]$ Minimum number of operations for matching

removing$F[i][j]=min(F[i][j],f[i-1][j]+2)$ Because to delete it, you must move the cursor to the$i$ before that, so the transfer is done with$f$arrays
Not deleted If$s[i]=t[j]$ , $F[i][j]=min(F[i][j],F[i-1][j-1])$ It can be done without moving.

$G[i][j]$ Definitions and transfers are similar

The final answer is.

\[ \min {f[i][j] + g[i+1][j+1] + (f[i][j]!=0)} \]

The last one ishome Cost of operation

This question card space with$short$ (because you can't use rolling arrays).

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,inf=N;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T,n,m;
short f[N][N],g[N][N],F[N][N],G[N][N];
char s[N],t[N];
int Min(int x,int y){ //It's handwritten becauseminincomparable short cap (a poem) int
	if(x>y) return y;
	return x;
}
signed main(){
	T=read();
	while(T--){
		n=read(),m=read();
		scanf("%s%s",s+1,t+1);
		for(int i=0;i<=n+1;i++){
			for(int j=0;j<=m+1;j++){
				F[i][j]=G[i][j]=f[i][j]=g[i][j]=inf;
			}
		}
		
		F[0][0]=f[0][0]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=m;j++){ //Be careful to put j=0 cyclic
				F[i][j]=f[i][j]=f[i-1][j]+2;
				if(s[i]==t[j]) f[i][j]=Min(f[i][j],f[i-1][j-1]+1),F[i][j]=Min(F[i][j],F[i-1][j-1]);
			}
		}
		
		G[n+1][m+1]=g[n+1][m+1]=0;
		for(int i=n;i>=1;i--){
			for(int j=m+1;j>=1;j--){ //Be careful to put j=m+1 cyclic
				G[i][j]=g[i][j]=g[i+1][j]+1;
				if(s[i]==t[j]) g[i][j]=Min(g[i][j],g[i+1][j+1]+1),G[i][j]=Min(G[i][j],G[i+1][j+1]);
			}
		}
		
		int ans=inf;
		for(int i=0;i<=n;i++){
			for(int j=0;j<=m;j++){
				ans=min(ans,F[i][j]+G[i+1][j+1]+(F[i][j]!=0));
			}
		}
		
		if(ans==inf) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

20.CF1954D Colored Balls

Classical conclusion:The answer to a set of$max(\lceil \frac {sum}{2} \rceil,maxn)$
$sum$ is the total number of set elements.$maxn$ is the number of occurrences of the most frequently occurring number, and division rounds up to the nearest whole number.

Just backpack for the number of programs and multiply the answer.

code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e3+5,mod=998244353;
inline int read(){
	int w=1,s=0;
	char c=getchar();
	for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int n;
int a[N],f[N],g[N];
int calc(int x){
	if(x&1) return x/2+1;
	return x/2;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);
	int sum=0,ans=0;
	f[0]=1;
	for(int i=1;i<=n;i++){
		sum+=a[i];
		for(int j=N-1;j>=a[i];j--){
			g[j]=f[j-a[i]];
			(f[j]+=f[j-a[i]])%=mod;
		}
		for(int j=a[i];j<=sum;j++)
			(ans+=g[j]*max(calc(j),a[i]))%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

21.discolour

Big Idea:Given a sequence with one color in each position, find the minimum value of the sum of the squares of the number of colors in each segment by dividing the sequence into segments.

Violent DP$O(n^2)$: $f[i]$ denote$i$ The minimum value of a position dyed to the corresponding color, enumerated when transferring the$j$ , $f[i]=min(f[i],f[j]+calc(j,i)^2)$ calc indicates the number of colors

The classic set-up of - Consider the range of DP values:
Notice that the final answer must be no greater than n, because I could have just colored each time the length of the$1$ interval (math.)
So for the color count we just enumerate to the$\sqrt n$ can immediately (do sth)

Specifically: since we determine the number of colors, we must dye as many colors as possible at a time, and the number of colors we only need to know the last position of each color, so we only need to maintain the last$\sqrt n$ the last position of each color.$O(n \times \sqrt n)$divert or distract (attention etc)

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5,inf=5e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N],f[N];
unordered_map<int,int> pos;
set<int> s;
signed main(){
// freopen("","r",stdin);
// freopen("","w",stdout);
	while(scanf("%lld",&n)!=EOF){
		for(int i=1;i<=n;i++) a[i]=read(),f[i]=inf;
		int t=sqrt(n)+1+1;
		f[0]=0; //Be careful not to writef[1]=1
		();
		(0);
		for(int i=1;i<=n;i++){
			if(!pos[a[i]]||((pos[a[i]])==())){
				pos[a[i]]=i,(i);
				if(()>t) (());
			}
			else{
				(pos[a[i]]);
				pos[a[i]]=i;
				(pos[a[i]]);
			}
			int cnt=()-1;
			for(int x:s){
				if(cnt==0) break;
				f[i]=min(f[i],f[x]+cnt*cnt); //dyeing and staining[x+1,i]
				cnt--;
			}
		}
		printf("%lld\n",f[n]);
		for(int i=1;i<=n;i++) (a[i]);
	}
	return 0;
}

22.binary flip-flop

For the sequence of operations.
$(x_1,y_1),(x_2,y_2),...,(x_k,y_k)$
in the event that$x_i=x_j$ , then we can eliminate them, and the same goes for y.
Assuming that after elimination the remaining$a$ different$x$peace$b$ different from each other$y$So easy to get still left.$a\times m+b\times n-2\times a \times b$ classifier for individual things or people, general, catch-all classifier$1$We can absolutely enumerate this violently.$a$ cap (a poem)$b$, we just need to count the number of programs separately.

found$f[i][j]$ denotes a construct of length$i$ sequences${x_1,x_2,...,x_i}$After eliminating them as above, the remaining$j$ Number of programs, when transferring.

(prefix indicating ordinal number, e.g. first, number two etc)$i$ classifier for individual things or people, general, catch-all classifier$x$ and one of the preceding$x$ Offset, so$f[i-1][j+1] \times (j+1) \to f[i][j]$
(prefix indicating ordinal number, e.g. first, number two etc)$i$ classifier for individual things or people, general, catch-all classifier$x$ and any of the preceding$x$ It's all different, so$f[i-1][j-1] \times (n-j+1) \to f[i][j]$

$g[i][j]$Tongli, a city in Jiangsu Province, China

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3005,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,k,s; 
int f[N][N],g[N][N];
signed main(){
	n=read(),m=read(),k=read(),s=read();
	
	f[0][0]=1;
	for(int i=1;i<=k;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=f[i-1][j+1]*(j+1)%mod;
			if(j>0) (f[i][j]+=f[i-1][j-1]*(n-j+1)%mod)%=mod;
		}
	}
	
	g[0][0]=1;
	for(int i=1;i<=k;i++){
		for(int j=0;j<=m;j++){
			g[i][j]=g[i-1][j+1]*(j+1)%mod;
			if(j>0) (g[i][j]+=g[i-1][j-1]*(m-j+1)%mod)%=mod;
		}
	}
	
	int ans=0;
	for(int a=0;a<=n;a++){
		for(int b=0;b<=m;b++){
			if(a*m+b*n-2ll*a*b!=s) continue;
			if(a>k||b>k||((k-a)%2ll!=0)||((k-b)%2ll!=0)) continue;
			(ans+=f[k][a]*g[k][b]%mod)%=mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

23.Unstable Portal

found$f[i]$ indicate$i$ until (a time)$n$ the minimum expected cost, such that$f[n]=n$。

suppose that...$i$ All outgoing edges of$(t_j,p_j,w_j) (1 \le j \le cnt_i)$,$cnt_i$ be$i$ of the number of outgoing edges.
After we arrange the order of attempts in a certain order

\[Expectation =w_1 + p_1 \times f[t_1] + (1 - p_1) \times (w_2 + p_2 \times f[t_2] + (1 - p_2) \times (...) ) \]

Let's change the dollars appropriately so that$c_j=w_j+p_j \times f[t_j]$ (Not what the title describes$c$), then.

\[\begin{aligned} have expectations &=c_1+(1-p_1) \times (c_2+(1-p_2) \times (c_3+(1-p_3) \times (...) ) ) \\ &=c_1 + (1-p_1)\times c_2 + (1-p_1)\times (1-p_2) \times c_3 + ... \\ &= \sum_{j=1}^{cnt_i} (\prod_{k=1}^{j-1} 1-p_k) \times cj \\ \end{aligned} \]

To make it as small as possible, we considerneighborhood exchange (math.):
For two neighboring terms j,j+1, the
Original expected cost$= (1-p_1) \times (1-p_2)\times ...\times (1-p_{j-1})\times c_j + (1-p_1)\times (1-p_2)\times ...\times (1-p_{j-1})\times (1-p_j)\times c_{j+1}$
Cost after exchange =$= (1-p_1) \times (1-p_2)\times ...\times (1-p_{j-1})\times c_{j+1} + (1-p_1)\times (1-p_2)\times ...\times (1-p_{j-1})\times (1-p_{j+1})\times c_j$
The current term is smaller than the next, eliminating identical terms yields.
$c_j+(1-p_j)\times c_{j+1} < c_{j+1}+(1-p_{j+1})\times c_j$
Just write cmp according to this

code

include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m;
struct P{
	int t;
	double p;
	int w;
	double c;
};
vector<P> G[N];
double f[N];
bool cmp(P x,P y){
	return 1.0*+(1.)* < 1.0*+(1.)*;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int w=read();
		G[i].push_back({i+1,1.0,w,0});
	}
	for(int i=1;i<=m;i++){
		int s=read(),t=read();
		double p;
		cin>>p;
		int w=read();
		G[s].push_back({t,p,w,0});
	}
	f[n]=0;
	for(int u=n-1;u>=1;u--){
		for(int i=0;i<G[u].size();i++)
			G[u][i].c=G[u][i].w*1.0+G[u][i].p*f[G[u][i].t];
		sort(G[u].begin(),G[u].end(),cmp);
		double g=1;
		for(P e:G[u]){
			f[u]+=*g;
			g*=(1.);
		}	
	}
	
	printf("%.2lf",f[1]);
	return 0;

24.CF1444D Rectangular Polyline

There's not really any dynamic programming in this question, it's mostly about constructing that
Considering that this is a dynamic programming questionnaire and the solution is a bit complex, see specificallyBooksnow solutions
~~First of all, I'm lazy.~~。

Just be aware of what's involvedbitset optimization 01 backpack

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int T;
int n,m,l[N],p[N],sumx,sumy;
vector<int> x[2],y[2];
int dx[N],dy[N],cnt;
bitset<N*N> f[N];
signed main(){
	T=read();
	f[0][0]=1; //No need to repeat assignments
	while(T--){
		sumx=sumy=0;
		x[0].clear(),x[1].clear();
		y[0].clear(),y[1].clear();
		
		n=read();
		for(int i=1;i<=n;i++) l[i]=read(),sumx+=l[i];
		m=read();
		for(int i=1;i<=m;i++) p[i]=read(),sumy+=p[i];
		if(n!=m||(sumx&1)||(sumy&1)){
			puts("No");
			continue;
		}
		
		for(int i=1;i<=n;i++) f[i]=f[i-1]|(f[i-1]<<l[i]);
		if(!f[n][sumx/2]){
			puts("No");
			continue;
		}
		int lst=sumx/2;
		for(int i=n;i>=1;i--)
			if(lst>=l[i]&&f[i-1][lst-l[i]]) lst-=l[i],x[0].push_back(l[i]);
			else x[1].push_back(l[i]);
			
		for(int i=1;i<=m;i++) f[i]=f[i-1]|(f[i-1]<<p[i]);
		if(!f[m][sumy/2]){
			puts("No");
			continue;
		}
		lst=sumy/2;
		for(int i=m;i>=1;i--)
			if(lst>=p[i]&&f[i-1][lst-p[i]]) lst-=p[i],y[0].push_back(p[i]);
			else y[1].push_back(p[i]);
			
		if(x[0].size()>y[0].size()) swap(x[0],x[1]);
		if(x[0].size()>y[0].size()) swap(y[0],y[1]);
		
		puts("Yes");
		cnt=0;
		for(int v:x[0]) dx[++cnt]=v;
		for(int v:x[1]) dx[++cnt]=v;
		cnt=0;
		for(int v:y[0]) dy[++cnt]=v;
		for(int v:y[1]) dy[++cnt]=v;
	
		sort(dx+1,dx+x[0].size()+1,greater<int>());
		sort(dx+x[0].size()+1,dx+y[0].size()+1,greater<int>());
		sort(dx+y[0].size()+1,dx+n+1,greater<int>());
		
		sort(dy+1,dy+x[0].size()+1);
		sort(dy+x[0].size()+1,dy+y[0].size()+1);
		sort(dy+y[0].size()+1,dy+m+1);
		int X=0,Y=0;
		for(int i=1;i<=x[0].size();i++){
			X+=dx[i];printf("%d %d\n",X,Y);
			Y+=dy[i];printf("%d %d\n",X,Y);
		}
		for(int i=x[0].size()+1;i<=y[0].size();i++){
			X-=dx[i];printf("%d %d\n",X,Y);
			Y+=dy[i];printf("%d %d\n",X,Y);
		}
		for(int i=y[0].size()+1;i<=n;i++){
			X-=dx[i];printf("%d %d\n",X,Y);
			Y-=dy[i];printf("%d %d\n",X,Y);
		}
	}
	return 0;
}

25.CF1178F1 Short Colorful Strip

This is a weaker version of the F question, which guarantees that the final sequence is an alignment.

It is clear that the two staining operations are either contained or separate, and definitely not intersecting.

Consider the interval DP.$f[i][j]$ Indicates that the interval is dyed out$[i,j]$ Number of programs
Obviously the color we dye first must be the smallest one, assuming that the position of that color is$k$。
Enumerate the first coloring interval$[x,y]$Obviously.$[x,y]$ embody$k$ ，
assume (office)$l \le x \le k \le y \le r$。
Because you can't dye it in the back.$k$ This position is now, and the staining operation is absolutely impossible to intersect, so the interval.$[l,x-1],[x,k-1],[k+1,y],[y+1,r]$ are independent, just multiply their program numbers together.
Note that here the order of each interval is unique (according to the smallest color), so there is no need to multiply the$4!$
Namely.

\[ f[l,r]=\sum_{x=l}^{k}\sum_{y=k}^{r}(f[l,x-1] \times f[x,k-1]) \times (f[k+1,y] \times f[y+1,r]) \]

Notice that this is$O(n^4)$ Soparticle marking the following noun as a direct object$x,y$ Just disassemble the enumeration:

\[ f[l,r]=(\sum_{x=l}^{k}f[l,x-1] \times f[x,k-1]) \times (\sum_{y=k}^{r}f[k+1,y] \times f[y+1,r]) \]

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,a[505],f[505][505];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++) a[i]=read();
	for(int l=0;l<=m+1;l++){
		for(int r=0;r<=m+1;r++){
			f[l][r]=1;
		}
	}
	for(int len=1;len<=m;len++){
		for(int l=1;l+len-1<=m;l++){
			int r=l+len-1;
			if(len>1){
				int sum1=0,sum2=0,ming=INT_MAX,pos;
				for(int i=l;i<=r;i++)
					if(a[i]<ming) ming=a[i],pos=i;
				for(int x=l;x<=pos;x++) (sum1+=f[l][x-1]*f[x][pos-1])%=mod;
				for(int y=pos;y<=r;y++) (sum2+=f[pos+1][y]*f[y+1][r])%=mod;
				f[l][r]=sum1*sum2%mod;
			}
		}
	}
	printf("%lld\n",f[1][m]);
	return 0;
}

26.CF1178F2 Long Colorful Strip

The only difference between this question and the previous one is : this one has a long paper tape and not necessarily only one of each color.
To apply the interval DP approach of the previous question, consider how to narrow the$m$。
Noting that a color segment from the beginning of theMaximum increase per operation$2$ color bandThat is, if the number of end-state color segments$>2\times n+1$That's definitely unresolved.
And for the color segments of a final state, they must have been colored together, otherwise it would not be possible to color them together later to the target color, and so all color segments can be viewed as a single point, so that there are at most$2 \times n+1$ points due to$O(n^3)$ Definitely not enough to run, so you can take a page from the previous question.

Because there is not necessarily only one of each color, i.e. each interval$[l,r]$ doesn't necessarily have to be the smallest color, so our enumeration of the$[x,y]$ To include all the$k_1,k_2,k_3,k_4,...k_{cnt}$。

The transferred equation is.

\[\begin{aligned} f[l,r] &=\sum_{x=l}^{k_1}\sum_{y=k_{cnt}}^{r}f[l,x-1] \times f[x,k_1-1] \times f[k_1+1,k_2-1] \times ... \times f[k_{cnt-1}+1,k_{cnt}-1] \times f[k_{cnt}+1,y] \times f[y+1,r]\\ &=(\sum_{x=l}^{k_1}f[l,x-1] \times f[x,k1-1]) \times (\sum_{y=k_{cnt}}^{r}f[kcnt+1,y] \times f[y+1,r]) \times (f[k1+1,k2-1] \times ... \times f[k[cnt-1]+1,kcnt-1]) \end{aligned} \]

Another detail to keep in mind when realizing this is that, for example, the sample: the2 1 2
Although this look is$0$ , but the program will output$4$。
This is because when we base$1$ Split it into$2$ cap (a poem)$2$ In two halves.These two halves are not independentI'm going to dye them.$2$It is inevitable that you will have to go through$1$。
The special verdict is also very well handled: if the$[l,r]$ If a color does not appear in all of the colors in this interval, set its DP value to$0$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m;
int a[N],b[N],f[1005][1005],pre[1005][505];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		b[i]=read();
	}
	int cnt=0;
	for(int i=1;i<=m;i++){
		int j;
		for(j=i;b[j]==b[i];j++) ;
		a[++cnt]=b[i],i=j-1;
	}
	m=cnt;
	if(m>2*n+1){
		printf("%d\n",0);
		return 0;	
	} 
	for(int i=1;i<=m;i++){
		pre[i][a[i]]=1;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			pre[i][j]+=pre[i-1][j];
		}
	}
	for(int l=0;l<=m+1;l++){
		for(int r=0;r<=m+1;r++){
			f[l][r]=1;
		}
	}
	for(int len=1;len<=m;len++){
		for(int l=1;l+len-1<=m;l++){
			int r=l+len-1;
			for(int i=l;i<=r;i++){
				int cnt1=pre[r][a[i]]-pre[l-1][a[i]],cnt2=pre[m][a[i]];
				if(cnt1<cnt2){
					f[l][r]=0;
					break;
				}
			}
			if(len>1){
				int sum1=0,sum2=0,tmp=1,ming=INT_MAX;
				for(int i=l;i<=r;i++)
					if(a[i]<ming) ming=a[i];
				int st=-1,ed=-1,lst=-1;
				for(int i=l;i<=r;i++){
					if(a[i]==ming){
						if(lst!=-1)
							(tmp*=f[lst+1][i-1])%=mod;
						if(st==-1) st=i;
						lst=ed=i;
					}
				}
				for(int x=l;x<=st;x++) (sum1+=f[l][x-1]*f[x][st-1])%=mod;
				for(int y=ed;y<=r;y++) (sum2+=f[ed+1][y]*f[y+1][r])%=mod;
				f[l][r]*=sum1*sum2%mod*tmp%mod;
			}
		}
	}
	printf("%lld\n",f[1][m]);
	return 0;
}

27.[CEOI2016] kangaroo

The title requirement is equivalent to saying that you can only jump back and forth across the room.

is equivalent to constructing a permutation which satisfies:
For each consecutive three numbers, the one in the middle is either the largest or the smallest, i.e.The whole sequence is wavy。

On such questions where the sequence satisfies a certain shape, the formula isConsider inserting each position from smallest to largest。
found$f[i][j]$ Indicates an insertion into the$i$ , in total$j$ The case of consecutive segments, followed by the case of the$i+1$ If$i+1 \ne s or t$There are three scenarios.

A self-contained section, i.e., inserted in the gap, with a total of$j+1$ gap, but if at this point it has been inserted into the$s$maybe$t$ Heads or tails can't be inserted.
Join the two segments together at this point$i+1$ must be greater than its left and right numbers (because it is from smallest to largest), i.e., he is the crest of the wave, must satisfy the meaning of the question, there are a total of$j-1$ options
Add at the beginning or end of a paragraph , assuming that the connection is at the beginning, then at this time the right side of i + 1 is smaller than it, but the left side, because it has not yet been placed, it must be larger than it by then, so there will be a monotonically diminishing number of three, which does not meet the meaning of the question, so it will not happen. (Of course, if$i+1=s or t$It's OK when it's not)

The code uses a fill-in-the-blank method in the$i=s or t$ If you want to make a special judgment, you can only put it at the beginning/end of the sentence.

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5,mod=1e9+7;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,s,t,f[N][N]; 
signed main(){
	n=read(),s=read(),t=read();
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(i==s||i==t) f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
			else f[i][j]=((j-(i>s)-(i>t))*f[i-1][j-1]%mod+j*f[i-1][j+1]%mod)%mod;
		}
	}
	printf("%lld\n",f[n][1]);
	return 0;
}

28.CF1312D Count the Arrays

The setup is similar to the previous question.

Let's assume for a moment that we are using the given$n-1$ number to construct this sequence.
We considerrange from large to smallConsider this.$n-1$ Number of individuals.

found$f[i][0/1]$ means that the construction length is$i$ and there are no/two identical numbers, then for

$f[i][0]$ : I can put the number I'm currently considering at the beginning of the sequence, or at the end.$f[i][0]\gets 2 \times f[i-1][0]$
$f[i][1]$ : If this number is not the same number then$f[i][1]\gets2* \times[i-1][1]$Otherwise I'd put one at the beginning and one at the end.$f[i][1] \gets f[i-2][0]$

We just need to randomly select from the$m$ Choose from a number of$n-1$ The answer is$f[n][1] \times C_m^{n-1})$

A few details.

$i=1$When it is placed at the beginning and the end it is the same, no need to$\times2$
only if$i \ge 3$late for$f[i][1] \gets f[i-2][0]$ of the transfer, otherwise it does not satisfy theseveritytedious

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,mod=998244353;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,f[N][2];
int inv[N],fact[N],q[N];
int C(int n,int m){
	if(n<m) return 0;
	return fact[n]*q[m]%mod*q[n-m]%mod; 
}
signed main(){
	n=read(),m=read();
	fact[0]=1;
	for(int i=1;i<N;i++) fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	q[0]=1;
	for(int i=1;i<N;i++) q[i]=q[i-1]*inv[i]%mod;

	f[0][0]=1;
	for(int i=1;i<=n;i++){
		if(i==1){
			(f[i][0]=f[i-1][0])%=mod;
			(f[i][1]=f[i-1][1])%=mod;
		}
		else{
			(f[i][0]=2*f[i-1][0])%=mod;
			(f[i][1]=2*f[i-1][1])%=mod;
		}
		if(i>=3) (f[i][1]+=f[i-2][0])%=mod;
	}
	printf("%lld\n",f[n][1]*C(m,n-1)%mod);
	return 0;
}

29.CF1312E Array Shrinking

Consider interval DP, one interval$[l,r]$ Either you can directly synthesize a number, or else you can definitely find a dividing point$i$, make$f[l][r]=f[l][i]+f[i+1][r]$, it is sufficient to perform the DP separately.

code

#include<bits/stdc++.h>
using namespace std;
const int N=500+5;
inline int read(){
    int w = 1, s = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,a[N];
int f[N][N]; //f[l][r]indicate[l,r]Minimum length remaining
int g[N][N]; //g[l][r]indicate区间[l,r]Value when reduced to a number，If you can't.=0
signed main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			if(len==1) g[l][r]=a[l];
			else if(len==2){
				if(a[l]==a[r]) g[l][r]=a[l]+1;
			}
			else{
				for(int i=l;i<=r;i++){
					if(g[l][i]==g[i+1][r]&&g[l][i]!=0){
						g[l][r]=g[l][i]+1;
						break;
					}
				}
			}
		}
	}
	for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			f[l][r]=r-l+1;
			if(g[l][r]) f[l][r]=1;
			else{
				for(int i=l;i<=r;i++){
					f[l][r]=min(f[l][r],f[l][i]+f[i+1][r]);
				}
			}
		}
	}
	printf("%d\n",f[1][n]);
	return 0;
}

30.CF1312G Autocompletion

First of all you can build a Trie according to the title (this is built in a bit of a strange way, you can see the code)

suppose that...$f[i]$ Indicates that the printout of the$i$ the minimum spend required for the string corresponding to node no.$id[i]$ indicate$i$ The string corresponding to node no.$S$ The dictionary sequence in the

Make a Tree DP:$f[i]=min(f[fa]+1,f[j]+id[i]-id[j])$of which$j$ be$i$ The ancestor of the$j$ The string represented by$i$ The prefix.
Considering the optimization of the transfer behindUse a stack to store$f[i]-id[i]$，
After traversing to the$i$ If the value at the top of the stack is larger than mine, it goes on the stack, and backtracks if it's on the stack, it goes off the stack.This way, you can just take out the top of the stack when transferring, and it guarantees that everything on the stack must be an ancestor of i

$id$ The array doesn't really have to be built either, it just needs to be maintained with variables, except that those nodes that aren't in S can't be counted.

code

#include<bits/stdc++.h>
#define PII pair<int,int>.
#define fi first
#define se second
using namespace std.
const int N=1e6+5; #define fi first; #define se second; #define fi first
inline int read(){
    int w = 1, s = 0; char c = getchar(); inline int read(){
    char c = getchar(); for (; c < '0' | '0')
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar()); for (; c < '0' || c > '9')
    for (;; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar());
    return s * w;
}
int n,m,id,a[N].
int ch[N][30],f[N];
bool stater[N];
stack<PII> st;;
void dfs(int u){ //traversing to u when f[u] has been counted out
if(! ()||(().se>f[u]-id)) ({u,f[u]-id}).
id+=stater[u]; //Here id actually indicates the number in S that is smaller than its dictionary order
for(int i=0;i<=25;i++){
if(!ch[u][i]) continue;
int v=ch[u][i];
f[v]=f[u]+1;
if(()&&stater[v]) f[v]=min(f[v],().se+id+1);
/*)
First, the result of auto-completion is a string in S, so stater[v]=true is satisfied.
Secondly, id[v]-id[u] here means the number of dictionary sequences smaller than v from u to v (including u, excluding v), but in fact v is to be counted, so +1 is needed.
*/dfs(v); dfs(v); dfs(v); dfs(v)
dfs(v); }
}
if(()&&().fi==u) (); }
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
int x=read();
char c;
cin>>c;
ch[x][c-'a']=i;
}
int m=read();
for(int i=1;i<=m;i++){
a[i]=read();
stater[a[i]]=true;
}

dfs(0);

for(int i=1;i<=m;i++) printf("%d ",f[a[i]]);
printf("%d ",f[a[i]]); puts("");
return 0.
}