D - Secret Passage
Consider backward pushing: each time you select a previous character and throw it to the front, and then add a new character. Consider which characters will be thrown to the front. Obviously, it is necessary to delete as few characters as possible to meet the requirements. The rest is the original string suffix. Then each state can be represented by \ (i,j,k\), that is, the current string length is \ (i\), there are \ (j\) \ (0\), and \ (k\) \ (1\) to be inserted in the front.
The rest is a trivial dp.
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
typedef long long ll;
const int mod = 998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
int g[N][N][N],f[N][N][N],n;
// j zeros to add, k ones to add;
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);reverse(s+1,s+n+1);
s[n+1]='2';
f[0][0][0]=g[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
for(int k=0;j+k<=i;k++){
if(g[i][j][k]){
int _d=i-j-k+1;
int dir=s[_d]-'0';
g[i+1][j][k]=add(g[i][j][k],g[i+1][j][k]);
if(dir)g[i+1][j+1][k]=add(g[i+1][j+1][k],g[i][j][k]);
else g[i+1][j][k+1]=add(g[i+1][j][k+1],g[i][j][k]);
}
}
}
}
f[n][0][0]=1;
for(int i=n-1;i;i--){
for(int j=0;j<=i;j++){
for(int k=0;j+k<=i;k++){
int dir=s[i-j-k+1]-'0',dir2=s[i-j-k+2]-'0';
int nt[3];
nt[0]=j,nt[1]=k,nt[2]=0;nt[0]++;
if(nt[dir]){
nt[dir]--;
if(nt[dir2]&&(dir2==0||dir==0))nt[dir2]--;
}
f[i][j][k]|=f[i+1][nt[0]][nt[1]];
nt[0]=j,nt[1]=k;nt[1]++;
if(nt[dir]){
nt[dir]--;
if(nt[dir2]&&(dir2==1||dir==1))nt[dir2]--;
}
f[i][j][k]|=f[i+1][nt[0]][nt[1]];
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)for(int k=0;k+j<=i;k++)
if(f[i][j][k])ans=add(ans, g[i][j][k]);
cout << ans << endl;
return 0;
}
E - Permutation Cover
If and only if all permutations with length \ (k\) cover the whole sequence. Consider that if there are three permutations covering a point at the same time, we only need to consider two of them.
Finally, the enumeration needs to consider \ (k\) sequences, so each number needs to cover all sequences. Obviously, it needs at least \ (\lceil\frac{k}{2} \rceil\) and at most \ (k\).
Then it is not difficult to get: if and only if:
Now consider greed. Each time greed adds a new section of arrangement (which may coincide with the previous one). Considering that the current sequence is \ (S\), the last \ (k\) is \ (P\) (obviously a permutation), and \ (b\u i\) is added to \ (i\). Considering that there are \ (t\) remaining intervals, similar to the previous one, but the difference is that the first one is determined, so it is still possible when \ (\min (b\u I) *2 +1 = \max (b\u I) \), However, there must be an additional condition: all \ (i\) in \ (P\) must meet \ (b\u i=\max (b) \) before \ (b\u i=\min (b) \).
So after the length of the extension is determined, what remains is a simple greedy complexity \ (O(nk^2) \).
#include<bits/stdc++.h>
using namespace std;
const int K = 110, N = 1010;
int a[K],n,k;
int ret[N], curlen;
inline bool check(){
int mn=a[1], mx=a[1];
for(int i=1;i<=k;i++)mx=max(mx,a[i]), mn=min(mn,a[i]);
return mn*2>=mx;
}
int vis[K];
inline void merge(int *x,int *y,int *z,int len1,int len2){
int i=1,j=1;
int l=0;
while(i<=len1&&j<=len2){
if(x[i]<y[j])z[++l]=x[i++];
else z[++l]=y[j++];
}
while(i<=len1)z[++l]=x[i++];
while(j<=len2)z[++l]=y[j++];
}
int b[K], x[K], y[K], z[K], l1, l2, l3;
vector<int> solve_ext(int len){
l1=l2=l3=0;
for(int i=1;i<=k;i++)vis[i]=0,b[i]=a[i];
for(int i=0;i<k-len;i++){
vis[ret[curlen-i]]=curlen-i;
}
for(int i=1;i<=k;i++){if(!vis[i])b[i]--;if(b[i]<0)return vector<int>(1,k+1);}
int mn,mx;mn=mx=b[1];
for(int i=1;i<=k;i++){
mn=min(mn, b[i]);
mx=max(mx, b[i]);
}
if(mn*2>=mx){
vector<int> ret;
for(int i=1;i<=k;i++)if(!vis[i])ret.push_back(i);
return ret;
}
else if(mn*2+1==mx){
vector<int> res;
for(int i=1;i<=k;i++)if(!vis[i] && b[i]==mx)x[++l1]=i;
for(int i=1;i<=k;i++)if(!vis[i] && b[i]==mn)x[++l1]=i;
for(int i=1;i<=k;i++)if(!vis[i] && b[i]!=mx && b[i]!=mn)y[++l2]=i;
merge(x,y,z,l1,l2);l3=l1+l2;
res=vector<int>(z+1,z+l3+1);
int p1=0,p2=0;
for(int i=curlen-(k-len-1);i<=curlen;i++){
if(b[ret[i]]==mx)p1=i;
if(b[ret[i]]==mn&&!p2)p2=i;
}
for(int i=1;i<=l3;i++){
if(b[z[i]]==mx)p1=i+curlen;
if(b[z[i]]==mn&&!p2)p2=i+curlen;
}
if(p1<p2)return res;
else return vector<int>(1,k+1);
}else
return vector<int>(1,k+1);
}
bool cmp(vector<int> a, vector<int> b){
for(size_t i=0;i<a.size();i++){
if(i>=b.size())return 1;
if(a[i]>b[i])return 1;
if(a[i]<b[i])return 0;
}
return 0;
}
inline void extend(){
vector<int> ext(1,k+1);
for(int extlen=1;extlen<=k&&curlen+extlen<=n;extlen++){
int d=k-extlen;
if(curlen-d+1>0){
vector<int> nw=solve_ext(extlen);
if(cmp(ext,nw))ext=nw;
}
}
for(size_t i=0;i<ext.size();i++){
printf("%d ",ext[i]);
ret[++curlen]=ext[i];
a[ext[i]]--;
}
return ;
}
int main()
{
cin >> k;#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int mod;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
int n,_lim;
int binom[N][N],fac[N];
int dp[N][N];
inline int getmat(int k,int l,int lim){
for(int i=1;i<=l;i++){
for(int j=0;j<k;j++){
if(i==1&&!j)dp[i][j]=1;
else dp[i][j]=0;
if(i)dp[i][j]=add(dp[i][j],dp[i-1][j]);
if(j)dp[i][j]=add(dp[i][j],dp[i][j-1]);
if(l-i+1+j-1>lim&&j)dp[i][j]=0;
}
for(int j=0;j<k;j++)if(k-j+i-1>lim)dp[i][j]=0;
}
int ans=0;
for(int j=1;j<k;j++)ans=add(ans, dp[l][j]);
return ans;
}
inline int solve(int lim,int n){
if(n==1)return 0;
if(n==0)return 1;
if(lim<0)return 0;
int ret=0;
for(int k=1;k-1<=lim&&k<=n;k++){
int tmp=mul(binom[n-1][k-1],mul(fac[n-k],fac[k-1]));
ret=add(ret,mul(tmp, getmat(k,n-k,lim)));
}
return ret;
}
int main()
{
cin >> n >> _lim >> mod;
for(int i=0;i<=n;i++)for(int j=binom[i][0]=1;j<=i;j++)binom[i][j]=add(binom[i-1][j],binom[i-1][j-1]);
for(int i=fac[0]=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
int ans=0;
for(int i=0;i<=_lim+1;i++){
ans=add(ans, mul(mul(fac[i],binom[n][i]),solve(_lim-i, n-i)));
}
cout << ans << endl;
}
for(int i=1;i<=k;++i)scanf("%d",&a[i]),n+=a[i];
if(!check()){puts("-1");return 0;}
while(curlen<n){extend();}puts("");
}
F - Forbidden Tournament
The graph must be a stack of strong connected components with the size of \ (1\) in front, followed by a large connected component.
First enumerate this length, and the rest is to find \ (n-i\) points. The degree of penetration is less than or equal to \ (k-i\), and the whole graph is required to be strongly connected components. We will consider solving this problem.
Considering all outgoing degrees (T\) of node \ (1\), the remaining point set is \ (S\). Obviously, it is impossible to have three circles in \ (S\), because all three points point to \ (1\).
Consider the node set \ (W\) with edges connected to the \ (S\) set, and the rest is \ (W_2\), obviously \ (W\) cannot be an empty set. Consider that if \ (x\) in \ (t\) points to \ (y\) in \ (t\), and \ (t\) in \ (S\), four nodes \ (x,t,1,y\) do not meet the requirements. So \ (y\) should also point to \ (t\). Therefore, all nodes in \ (W_2\) do not have the entry edge in \ (W\), and there are no three rings in \ (W\) (otherwise, the three points must point to one node at the same time). Because both sides of \ (W_2\) are connected to the points in \ (W\), neither \ (W_2\) can have three rings.
So \ (T\) is also a \ (\text{DAG}\).
Now, the points in \ (S\) are sorted in topological order \ (x\u 1, x\u 2, \cdots, x\u k\), \ (T\) are similarly arranged in \ (y\u 1, y\u 2, \cdots, y\u l\). We just need to consider the side between them. Write it as a matrix.
Because \ (y\u i\) is connected to \ (x\u t\), then \ (\forall j\ge I, t\u j\) is connected to \ (x\u t\) (SSE). Therefore, there must be \ (y\u l\to x\u 1\) (otherwise \ (x\u 1\) has no penetration and is not a strongly connected component). Then consider \ (y\u I, y\u L, x\u 1, x\u t\), including: \ (y\u i\to y\u l\to x\u 1, x\u 1\to x\u T, y\u l\to x\u t\), so it must be \ (y\u l\to x\u. Continue to consider: for \ (\forall j\ge i\), there are \ (y\u j\to x\u 1, y\u j\to x\u t\). Then consider: \ (y_j,y_l,x_1,x_t\), and you can get \ (y_j\to x\u t\).
So if \ ((i,j)=1\) on the matrix represents \ (y\u j\to x\u i\), then \ ((i,j)=1\) can get \ ((i-1,j)=1, (i,j+1) =1\). The rest is a simple dp.
Complexity \ (O(n^4) \).
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int mod;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
int n,_lim;
int binom[N][N],fac[N];
int dp[N][N];
inline int getmat(int k,int l,int lim){
for(int i=1;i<=l;i++){
for(int j=0;j<k;j++){
if(i==1&&!j)dp[i][j]=1;
else dp[i][j]=0;
if(i)dp[i][j]=add(dp[i][j],dp[i-1][j]);
if(j)dp[i][j]=add(dp[i][j],dp[i][j-1]);
if(l-i+1+j-1>lim&&j)dp[i][j]=0;
}
for(int j=0;j<k;j++)if(k-j+i-1>lim)dp[i][j]=0;
}
int ans=0;
for(int j=1;j<k;j++)ans=add(ans, dp[l][j]);
return ans;
}
inline int solve(int lim,int n){
if(n==1)return 0;
if(n==0)return 1;
if(lim<0)return 0;
int ret=0;
for(int k=1;k-1<=lim&&k<=n;k++){
int tmp=mul(binom[n-1][k-1],mul(fac[n-k],fac[k-1]));
ret=add(ret,mul(tmp, getmat(k,n-k,lim)));
}
return ret;
}
int main()
{
cin >> n >> _lim >> mod;
for(int i=0;i<=n;i++)for(int j=binom[i][0]=1;j<=i;j++)binom[i][j]=add(binom[i-1][j],binom[i-1][j-1]);
for(int i=fac[0]=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
int ans=0;
for(int i=0;i<=_lim+1;i++){
ans=add(ans, mul(mul(fac[i],binom[n][i]),solve(_lim-i, n-i)));
}
cout << ans << endl;
}