T1 魔法
解题思路
发现选择情况无非就是两种，连续的一段或者间隔为 \(R+B\) 的倍数的一段。
直接对于原序列贪心，每次选择可以消除的部分并将其删掉。
对于合法的情况将操作倒序输出即可。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10;
int n,r,b,head,tail,cntr,cntb,que[N];
char ch[N];
vector<int> ans;
void print()
{
printf("YES\n%lld",n/(r+b));
for(int i=n-1;~i;i--)
{
if((n-i-1)%(r+b)==0) printf("\n");
printf("%lld ",ans[i]);
}
}
bool solve_front()
{
multiset<int> res;
for(int i=1;i<=n;i++) res.insert(i);
while(res.size())
{
bool flag=false; head=1; tail=cntr=cntb=0;
for(auto it=res.begin();it!=res.end();it++)
{
int i=(*it); que[++tail]=i; cntr+=(ch[i]=='R'); cntb+=(ch[i]=='B');
if(tail>r+b) cntr-=(ch[que[head]]=='R'),cntb-=(ch[que[head]]=='B'),head++;
if(cntr==r&&cntb==b&&tail>=r+b){flag=true;break;}
}
if(!flag) return false;
for(int i=head;i<=tail;i++)
ans.push_back(que[i]),
res.erase(res.find(que[i]));
}
return true;
}
#undef int
int main()
{
#define int long long
freopen("magic.in","r",stdin); freopen("magic.out","w",stdout);
n=read(); r=read(); b=read(); scanf("%s",ch+1);
for(int i=1;i<=n;i++) cntr+=(ch[i]=='R'),cntb+=(ch[i]=='B');
if((!r&&cntr)||(!b&&cntb)) printf("NO"),exit(0);
if((r&&cntr%r)||(b&&cntb%b)) printf("NO"),exit(0);
if(solve_front()) print();
else printf("NO");
return 0;
}
T2 连通性
解题思路
\(f(n,m)\) 表示 \(n,m\) 对应的答案， \(g(n)\) 表示点数为 \(n\) 的合法无向图的个数。
\(g(n)\) 可以通过容斥求出来，钦定枚举 1 所在联通块的点的大小
\[\displaystyle g(n)=2^{\frac{n(n-1)}{2}}-\sum_{i=1}^{n-1}g(i)\times 2^{\frac{(n-i)(n-i-1)}{2}}\times\binom{n-1}{i-1} \]对于 \(f(n,m)\) 的转移考虑两种情况
-
全部是没有循环到的点的联通块： \(\sum\limits_{i=1}^m f(n-i,m-i)\binom{m-1}{i-1}\)
-
计算联通块内有循环到的点的情况钦定 \(n\) 节点在最后一个： \(\sum\limits_{i=1}^m\sum\limits_{j=1}^{n-m}f(n-i-j,m-j)\binom{m-1}{i-1}\binom{n-m}{j}g(j)\times(2^j-1)^i\times 2^{\frac{(i-1)i}{2}}\)
第二个柿子的后半部分就是联通块内与外面的有连边的点数方案数，以及所连的点的方案数。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=110,mod=1e9+7;
int T,n,m,p2[N*N],f[N][N],g[N],h[N][N],fac[N],ifac[N];
int C(int x,int y){return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
int power(int x,int y,int p=mod)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%p;
x=x*x%p; y>>=1;
}
return temp;
}
int dfs(int n,int m)
{
if(~f[n][m]) return f[n][m];
if(!m) return f[n][m]=p2[n*(n-1)/2];
int rec=0;
for(int i=1;i<=m;i++) rec=(rec+dfs(n-i,m-i)*C(m-1,i-1))%mod;
for(int i=1;i<=m;i++) for(int j=1;j<=n-m;j++) rec=(rec+dfs(n-i-j,m-i)*C(m-1,i-1)%mod*C(n-m,j)%mod*h[i][j])%mod;
return f[n][m]=rec;
}
#undef int
int main()
{
#define int long long
freopen("floyd.in","r",stdin); freopen("floyd.out","w",stdout);
memset(f,-1,sizeof(f)); f[1][0]=f[0][0]=f[1][1]=1;
fac[0]=ifac[0]=p2[0]=1; for(int i=1;i<=100;i++) fac[i]=fac[i-1]*i%mod;
ifac[100]=power(fac[100],mod-2); for(int i=99;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1;i<=10000;i++) p2[i]=p2[i-1]*2%mod;
for(int i=1;i<=100;i++) g[i]=p2[i*(i-1)/2];
for(int i=1;i<=100;i++) for(int j=1;j<i;j++) g[i]=(g[i]-g[j]*p2[(i-j)*(i-j-1)/2]%mod*C(i-1,j-1)%mod+mod)%mod;
for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) h[i][j]=g[j]*power(p2[j]-1,i)%mod*p2[i*(i-1)/2]%mod;
T=read(); while(T--) n=read(),m=read(),printf("%lld\n",dfs(n,m));
return 0;
}
T3 矩形
解题思路
发现对于 L 以及 R 所对应的数字可以通过二分求出来。
直接枚举所有的数字，查询排名在 L 和 R 之间的数字，向 L,R 中间填就好了
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=3e5+10,INF=1e18,Lim=3e5*1e9;
int n,L,R,top,sta[N],s[N],l[N],r[N];
vector<int> ans;
int S(int x){return x<=0?0:x*(x+1)/2;}
int g(int w,int l,int r){return S(w)-S(w-l-1)-S(w-r-1)+S(w-l-r-2);}
int work(int x){if((--x)<=0)return 0;int sum=0;for(int i=1;i<=n;i++) sum+=g(min(x/s[i],r[i]-l[i]+1),i-l[i],r[i]-i);return sum;}
int divide(int num)
{
int li=0,ri=Lim,ans=0;
while(li<=ri)
{
int mid=(li+ri)>>1;
if(work(mid)<num) li=mid+1,ans=mid;
else ri=mid-1;
}
return ans;
}
#undef int
int main()
{
#define int long long
freopen("rectangle.in","r",stdin); freopen("rectangle.out","w",stdout);
n=read(); for(int i=1;i<=n;i++) s[i]=read(); L=read(); R=read();
sta[++top]=l[1]=1;
for(int i=2;i<=n;i++)
{
while(top&&s[i]<s[sta[top]]) r[sta[top--]]=i-1;
l[i]=sta[top]+1; sta[++top]=i;
}
while(top) r[sta[top--]]=n;
int posl=divide(L),posr=divide(R),ending=min(R,work(posl+1));
for(int i=L;i<=ending;i++) ans.push_back(posl);
for(int i=1;i<=n;i++)
{
int up=max(r[i]-i+1,i-l[i]+1),down=min(r[i]-i+1,i-l[i]+1);
int fro=posl/s[i]+1,to=min(r[i]-l[i]+1,(posr-1)/s[i]),cnt;
for(int j=fro;j<=to;j++)
{
cnt=(j<=down)?j:(j<=up?down:r[i]-l[i]-j+2);
while(cnt--) ans.push_back(j*s[i]);
}
}
while(ans.size()<=R-L) ans.push_back(posr); sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++) printf("%lld ",ans[i]);
return 0;
}