这场比赛打完后可以找何神玩了orz(orz)*
嘿嘿嘿。输出n/2+m/2即可。
我能说我智商捉鸡想了4min吗？
由于N个点的连通块最少有N-1条边，所以至多删两条。
暴力枚举然后并查集判判即可。
奥妙重重的数位dp。
设f[i][j][d1][d2][d3]表示前i位，x1与x2的数位差为j。大小关系如下：
d1=0 x1<x2
d1=1 x1=x2
d1=2 x1>x2
d2=0 x1<=n
d2=1 x1>n
d3=0 x2<=n
d3=1 x2>n
然后滚动数组DP一下。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int mod=;
const int maxn=;
struct bign {
int s[maxn],len;
bign operator = (const char* a) {
memset(s,,sizeof(s));len=strlen(a);
rep(i,,len-) s[i]=a[len-i-]-'';
}
void operator /= (int b) {
int x=;
dwn(i,len-,) {
int v=s[i]+x;
s[i]=v/;
x=(v%)*;
}
while(!s[len-]&&len>) len--;
}
void print() {
dwn(i,len-,) printf("%d",s[i]);
puts("");
}
}N;
char s[maxn];
int bit[maxn];
ll f[][maxn*][][][];
void solve() {
scanf("%s",s);N=s;int n=;
while(N.s[]||N.len!=) bit[++n]=N.s[]&,N/=;
memset(f,,sizeof(f));
int cur=;f[][n][][][]=;
rep(i,,n-) {
cur^=;memset(f[cur],,sizeof(f[cur]));
rep(j,-i+n,i+n) rep(d1,,) rep(d2,,) rep(d3,,) {
ll& ans=f[cur^][j][d1][d2][d3];
(f[cur][j][d1][bit[i+]?:d2][bit[i+]?:d3]+=ans)%=mod;
(f[cur][j][d1][(!bit[i+])?:d2][(!bit[i+])?:d3]+=ans)%=mod;
(f[cur][j+][][(!bit[i+])?:d2][bit[i+]?:d3]+=ans)%=mod;
(f[cur][j-][][bit[i+]?:d2][(!bit[i+])?:d3]+=ans)%=mod;
}
}
ll ans=;
rep(i,n+,*n) (ans+=f[cur][i][][][])%=mod;
printf("%lld\n",ans);
}
int main() {
int T=read();
while(T--) solve();
return ;
}
我选择go die。
考虑用线段树来做。
对于操作1，暴力变换带标记且不全为1的区间。
对于操作2，在线段树上打标记。
对于操作3，线段树上直接查询。
等等，我们写程序要讲道理对不对。
我们发现对于一个[1,10^7]的数x，最多执行logx次操作1x就变成了1。
我们可以进行势能分析，初始势能为nlogx。
对于操作1，每变换一次势能-1。
对于操作2，至多增加log^2n的势能。
对于操作3，时间复杂度恒定O(logn)
所以总时间复杂度O(nlog^2n)
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int N=;
const int maxn=;
int vis[N],phi[N],pri[N/],cnt;
void gen(int n) {
phi[]=;
rep(i,,n) {
if(!vis[i]) pri[++cnt]=i,phi[i]=i-;
rep(j,,cnt) {
if(i*pri[j]>n) break;
vis[i*pri[j]]=;
if(i%pri[j]==) {phi[i*pri[j]]=phi[i]*pri[j];break;}
phi[i*pri[j]]=phi[i]*(pri[j]-);
}
}
}
ll sumv[maxn*],is[maxn*],setv[maxn*];
void pushdown(int o,int l,int r) {
if(setv[o]) {
int lc=o<<,rc=lc|,mid=l+r>>;
setv[lc]=setv[rc]=setv[o];
is[lc]=is[rc]=;
sumv[lc]=setv[o]*(mid-l+);
sumv[rc]=setv[o]*(r-mid);
setv[o]=;
}
}
void maintain(int o,int l,int r) {
int lc=o<<,rc=lc|;
if(setv[o]) sumv[o]=(r-l+)*setv[o],is[o]=(setv[o]!=);
else sumv[o]=sumv[lc]+sumv[rc],is[o]=is[lc]|is[rc];
}
void update(int o,int l,int r,int ql,int qr,int v) {
if(ql<=l&&r<=qr) setv[o]=v;
else {
pushdown(o,l,r);
int lc=o<<,rc=lc|,mid=l+r>>;
if(ql<=mid) update(lc,l,mid,ql,qr,v);
if(qr>mid) update(rc,mid+,r,ql,qr,v);
}
maintain(o,l,r);
}
void update2(int o,int l,int r,int ql,int qr) {
if(ql<=l&&r<=qr&&setv[o]) setv[o]=phi[setv[o]];
else {
pushdown(o,l,r);
int lc=o<<,rc=lc|,mid=l+r>>;
if(ql<=mid&&is[lc]) update2(lc,l,mid,ql,qr);
if(qr>mid&&is[rc]) update2(rc,mid+,r,ql,qr);
}
maintain(o,l,r);
}
void build(int o,int l,int r) {
sumv[o]=is[o]=setv[o]=;
if(l==r) setv[o]=read();
else {
int lc=o<<,rc=lc|,mid=l+r>>;
build(lc,l,mid);build(rc,mid+,r);
}
maintain(o,l,r);
}
ll query(int o,int l,int r,int ql,int qr) {
if(ql<=l&&r<=qr) return sumv[o];
pushdown(o,l,r);
int lc=o<<,rc=lc|,mid=l+r>>;ll ans=;
if(ql<=mid) ans+=query(lc,l,mid,ql,qr);
if(qr>mid) ans+=query(rc,mid+,r,ql,qr);
return ans;
}
void solve() {
int n=read(),m=read();
build(,,n);
while(m--) {
int t=read(),l=read(),r=read();
if(t==) update2(,,n,l,r);
else if(t==) update(,,n,l,r,read());
else printf("%lld\n",query(,,n,l,r));
}
}
int main() {
gen();
dwn(T,read(),) solve();
return ;
}
