北京集训的第一天，我完美爆零......

这其中的经历，十分有趣呢。

T1:

这题一看就是先猜一个性质然后利用他去求解。

如果我们知道怎么插入，怎么判定的话，可以线段树分治的说。

然后我猜了一个结论:如果稳定，则一定有一个x的四联通块能同时通向上下左右边界。

乍一看是对的，实际上这个东西充分，但不必要。

考虑3*3的网格图，我们染色左下角三个点，再染色右上角三个点，结果应该是稳定的。

然后这个算法就错了。

问题是由于我太菜了，故考场上并没有想到这个反例......

正解的确是线段树分治，然而他是用角度推的。

考虑对于一个四边形的四个定点，每个点在左上角的那个角，显然对角线的角和相同。

而如果一个格子为x，则他右下角和左上角的角度均为90度，相当于让另外两个角必须满足某些条件。

而如果这个条件让整个图都被限制的话，显然就固定了。

现在我们可以做什么?O(nmq)暴力。

然而正解要更加优美:

显然我们可以用第一行的所有角度和第一列的所有角度算出所有角，所以限制就相当于是行列连边。

经典的二分图模型啦。

然后用可回退并查集维护是否左右行列都在一个联通块里就好了QwQ。

考场爆零代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define debug cout  7 using namespace std;  8 const int maxn=9e6+1e2,maxl=3e3+1e2,maxq=1e5+1e2;  9 const int dx[]={
    1,-1,0,0},dy[]={
    0,0,1,-1}; 10  11 char in[maxl][maxl],now[maxl][maxl]; 12 int tim[maxl][maxl],ans[maxq]; 13 int l[maxq<<3],r[maxq<<3],lson[maxq<<3],rson[maxq<<3],cnt; 14 int fa[maxn],siz[maxn],sta[maxn]; 15 int n,m,q; 16 int pp; 17  18 struct ONode { 19     int x,y; 20 }; 21 vector
           
             ns[maxq<<3]; 22 23 struct MemNode { 24 int *dst,val; 25 MemNode() {} 26 MemNode(int &x) { dst = &x , val = x; } 27 inline void res() { 28 *dst = val; 29 } 30 }stk[maxn]; 31 int top; 32 33 inline int findfa(int x) { 34 return fa[x] == x ? x : findfa(fa[x]); 35 } 36 inline bool merge(int x,int y) { 37 x = findfa(x) , y = findfa(y); 38 if( x == y ) return 0; 39 if( siz[x] < siz[y] ) swap(x,y); 40 if( pp != 1 ) stk[++top] = MemNode(siz[x]) , stk[++top] = MemNode(fa[y]) , stk[++top] = MemNode(sta[x]); 41 fa[y] = x , siz[x] += siz[y] , sta[x] |= sta[y]; 42 return sta[x] == 15; 43 } 44 45 inline void reset(int ltop) { 46 while( top > ltop ) stk[top].res() , --top; 47 } 48 inline int cov(int x,int y) { 49 return m * --x + y; 50 } 51 inline int operat(int x,int y) { 52 int ret = 0; 53 now[x][y] = 'x'; 54 ret |= ( sta[findfa(cov(x,y))] == 15 ); 55 for(int i=0;i<4;i++) { 56 const int tx = x + dx[i] , ty = y + dy[i]; 57 if( 0 < tx && tx <= n && 0 < ty && ty <= m && now[tx][ty] == 'x' ) ret |= merge(cov(x,y),cov(tx,ty)); 58 } 59 return ret; 60 } 61 62 inline void build(int pos,int ll,int rr) { 63 l[pos] = ll , r[pos] = rr; 64 if( ll == rr ) return; 65 const int mid = ( ll + rr ) >> 1; 66 build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+1,rr); 67 } 68 inline void insert(int pos,int ll,int rr,const ONode &o) { 69 if( ll <= l[pos] && r[pos] <= rr ) { 70 ns[pos].push_back(o); 71 return; 72 } const int mid = ( l[pos] + r[pos] ) >> 1; 73 if( rr <= mid ) insert(lson[pos],ll,rr,o); 74 else if( ll > mid ) insert(rson[pos],ll,rr,o); 75 else insert(lson[pos],ll,rr,o) , insert(rson[pos],ll,rr,o); 76 } 77 inline void dfs(int pos,int stable) { 78 pp = pos; 79 const int memtop = top; 80 for(unsigned i=0;i
           
          
         
        
       
      

考后AC代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define debug cout 8 using namespace std; 9 const int maxn=9e6+1e2,maxl=3e3+1e2,maxq=3e5+1e2;10 11 char in[maxl][maxl];12 int tim[maxl][maxl];13 int l[maxq<<2],r[maxq<<2],lson[maxq<<2],rson[maxq<<2],cnt;14 int fa[maxn],siz[maxn];15 int ans[maxq];16 int n,m;17 18 struct Node {19 int x,y;20 };21 vector
            
              ns[maxq<<2];22 struct StkNode {23 int *dst,val;24 StkNode() {}25 StkNode(int &x) { dst = &x , val = x; }26 inline void res() { *dst = val ; }27 }stk[maxq<<2];28 int top;29 30 inline int findfa(int x) {31 return fa[x] == x ? x : findfa(fa[x]);32 }33 inline void merge(int x,int y,int pos) {34 x = findfa(x) , y = findfa(y);35 if( x == y ) return;36 if( siz[x] < siz[y] ) swap(x,y);37 if( pos != 1 ) stk[++top] = StkNode(fa[y]) , stk[++top] = StkNode(siz[x]);38 fa[y] = x , siz[x] += siz[y];39 }40 inline void reset(int last) {41 while( top > last ) stk[top--].res();42 }43 44 inline void build(int pos,int ll,int rr) {45 l[pos] = ll , r[pos] = rr;46 if( ll == rr ) return;47 const int mid = ( ll + rr ) >> 1;48 build(lson[pos]=++cnt,ll,mid) , 49 build(rson[pos]=++cnt,mid+1,rr) ;50 }51 inline void insert(int pos,int ll,int rr,const Node &o) {52 if( ll <= l[pos] && r[pos] <= rr ) return ns[pos].push_back(o);53 const int mid = r[lson[pos]];54 if( rr <= mid ) return insert(lson[pos],ll,rr,o);55 if( ll > mid ) return insert(rson[pos],ll,rr,o);56 insert(lson[pos],ll,rr,o) , 57 insert(rson[pos],ll,rr,o) ;58 }59 inline void dfs(int pos) {60 const int mtop = top;61 for(unsigned i=0;i
            
           
          
         
        
       
      

T2:

前两个测试点可以大力状压哈希bfs(不，大力bfs是过不去第二个测试点的)。

然后我们考虑分析一发:

首先我们只有三根柱子(废话)。

考虑最大的位置不对的盘子，我们一定要把他从一根柱子移动到另一根。

也就是说，我们需要让他所在的柱子为只有他，他需要到的柱子为空。

其他的盘子呢?必须都移到剩下的一个柱子上啊。这个步数大力计算一下就好了。

然后我们移动了最大的盘子，现在我们有一摞盘子和他们需要的地方。

一个一个摆放到位就可以了，反正(大概)只有一种不走重复步的方案吧。

接着你会发现你会WA，你过不了样例。

因为样例的最优解是把最大的盘子先放到中间。

好，这也是一种策略，我们把第一步的这种方式也考虑进去，反正接下来对一摞盘子的分析一定是对的。

关于我为什么爆零?考场上以为1是最大的盘子，然后直接贪心过了样例，自然也没有想第二种情况啦......

其实更正了看错题的问题还是有60分的。

考场爆零代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
          
         
        
       
      

稍加修改的60分代码:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
          
         
        
       
      

考后AC代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define lli long long int 6 using namespace std; 7 const int maxn=1e6+1e2; 8 const int mod=998244353; 9 10 int st[maxn],ed[maxn],way1[maxn],way2[maxn];11 lli ans;12 13 inline void calc(int* dst,const int* sou,int pos,int tar) {14     if( !pos ) return;15     if( sou[pos] == tar ) return calc(dst,sou,pos-1,tar);16     ++dst[pos-1] , calc(dst,sou,pos-1,6-tar-sou[pos]);17 }18 inline void fix(int* dst,int len) {19     for(int i=0;i
          
           > 1 , dst[i] &= 1;21 }22 inline bool cmp(int* lhs,int* rhs,int len) {23     for(int i=len;~i;i--) if( lhs[i] != rhs[i] ) return lhs[i] < rhs[i];24     return 0;25 }26 inline lli getans(int* sou,int len) {27     lli ret = 0;28     for(int i=len;~i;i--) ret = ( ( ret << 1 ) + sou[i] ) % mod;29     return ret;30 }31 32 int main() {33     static int n,siz;34     scanf("%d",&n),siz=n;35     for(int i=1,p,x;i<=3;i++) {36         scanf("%d",&p);37         while(p--) scanf("%d",&x) , st[x] = i;38     }39     for(int i=1,p,x;i<=3;i++) {40         scanf("%d",&p);41         while(p--) scanf("%d",&x) , ed[x] = i;42     }43     while( st[siz] == ed[siz] ) --siz;44     if( !siz ) return puts("0"),0;45     calc(way1,st,siz-1,6-st[siz]-ed[siz]) , calc(way1,ed,siz-1,6-st[siz]-ed[siz]) , ++*way1;46     calc(way2,st,siz-1,ed[siz]) , calc(way2,ed,siz-1,st[siz]) , ++*way2 , ++way2[siz-1];47     fix(way1,n+3) , fix(way2,n+3);48     ans = cmp(way1,way2,n+3) ? getans(way1,n+3) : getans(way2,n+3);49     printf("%lld\n",ans);50     return 0;51 }
          
         
        
       
      

T3:

这一看就是神仙题啊，这东西人干事？

以下是官方的题解:

看不懂题解的我只好写了一个60分大力反演，弃坑了。

60分代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define lli long long int 7 #define debug cout 8 using namespace std; 9 const int maxn=1e6+1e2;10 const int mod=998244353;11 12 int bas[maxn],tim[maxn],mu[maxn];13 int n,D,L,R;14 15 inline lli fastpow(lli base,int tim) {16     lli ret = 1;17     while( tim ) {18         if( tim & 1 ) ret = ret * base % mod;19         if( tim >>= 1 ) base = base * base % mod;20     }21     return ret % mod;22 }23 inline int gcd(int x,int y) {24     if( ! ( x && y ) ) return x | y;25     register int t;26     while( ( t = x % y ) )27         x = y , y = t;28     return y;29 }30 31 inline void pre() {32     bas[1] = tim[1] = 1;33     for(int i=2;i<=n;i++) {34         if( !bas[i] ) for(lli j=i,cnt=1;j<=n;j*=i,++cnt) bas[j] = i , tim[j] = cnt;35     }36 }37 inline void sieve() {38     static int prime[maxn],cnt;39     static char vis[maxn];40     mu[1] = 1;41     for(int i=2;i<=n;i++) {42         if( !vis[i] ) prime[++cnt] = i , mu[i] = -1;43         for(int j=1;j<=cnt&&(lli)i*prime[j]<=n;j++) {44             const int tar = i * prime[j];45             vis[tar] = 1;46             if( ! ( i % prime[j]) ) break;47             mu[tar] = -mu[i];48         }49     }50 }51 52 inline lli force_g(int x,int sqt) {53     int g = gcd( sqt , tim[x] );54     return fastpow(fastpow(bas[x],tim[x]/g),sqt/g);55 }56 inline lli force(int x) {57     lli ret = 0;58     const int lim = (int) ( log2(x) * D + 1e-6 );59     for(int i=D;i<=lim;i+=D) {60         for(int j=1;j*i<=lim;j++)61             ret += mu[i/D] * mu[j] * fastpow(j,D) * force_g(x,i*j) % mod ,62             ret %= mod;63     }64     return ret;65 }66 67 int main() {68     static lli ans;69     scanf("%d%d%d%d",&n,&D,&L,&R) , pre() , sieve();70     for(int i=L;i<=R;i++) ( ans += force(i) ) %= mod;71     ans = ( ans % mod + mod ) % mod;72     printf("%lld\n",ans);73     return 0;74 }
          
         
        
       
      

然后把神仙写的标程丢上来好了，反正我已经凉了。

神仙题的std:

1 #include 
      
         2 using namespace std;  3    4 typedef long long lint;  5 typedef long double db;  6 const int N = 500010, MO = 998244353;  7    8 inline int add(int a,int b) { return (a+b)%MO; }  9 inline int mul(int a,int b) { return (lint)a*b%MO; } 10 inline int powmod(int a,int b)  11 { 12     int s = 1; 13     for(;b;b>>=1,a=mul(a,a)) if(b&1) s = mul(s,a); 14     return s; 15 } 16   17 int n,D,L,R; 18 int sk[N],mu[N],c[N],pr[N],np[N],ps; 19   20 void pre() 21 { 22     int i,j; np[1] = 1, mu[1] = 1; 23     for(i=2;i
       
        r) return 0; 43     k++; 44     int s = 0, top = min(k,r); 45     int i,j; 46     sk[1] = 1; 47     for(i=2;i<=top;i++) 48     { 49         if(!np[i]) sk[i] = powmod(i,k-1); 50         for(j=1;j<=ps&&pr[j]<=i&&i*pr[j]<=top;j++) 51         { 52             sk[i*pr[j]] = mul(sk[i],sk[pr[j]]); 53             if(i%pr[j]==0) break; 54         } 55     } 56     if(r<=k) 57     { 58         for(int i=l;i<=r;i++)  59             s = add(s,sk[i]); 60         return s; 61     } 62     for(i=1;i<=k;i++) sk[i] = add(sk[i],sk[i-1]); 63     static int fc[N],iv[N],ml[N],mr[N]; 64     fc[0] = 1, ml[0] = 1, mr[k] = 1; 65     for(i=1;i<=k;i++) fc[i] = mul(fc[i-1],i), ml[i] = mul(ml[i-1],r-k+i-1); 66     iv[k] = powmod(fc[k],MO-2); 67     for(i=k-1;i>=0;i--) mr[i] = mul(mr[i+1],r-k+i+1), iv[i] = mul(iv[i+1],i+1); 68     for(i=0;i<=k;i++) s = add(s,(MO+(i&1?-1:1)*mul(sk[k-i],mul(mul(ml[i],mr[i]),mul(iv[i],iv[k-i]))))%MO); 69   70     l--; 71     for(i=1;i<=k;i++) ml[i] = mul(ml[i-1],l-k+i-1); 72     for(i=k-1;i>=0;i--) mr[i] = mul(mr[i+1],l-k+i+1); 73     for(i=0;i<=k;i++) s = add(s,(MO-(i&1?-1:1)*mul(sk[k-i],mul(mul(ml[i],mr[i]),mul(iv[i],iv[k-i]))))%MO); 74     return s; 75 } 76   77 inline int rtceil(int a,int b) 78 { 79     int x = pow(a,1/(db)b); 80     while(pow(x,b)>a) x--; 81     while(pow(x,b)
        
         a) x--; 90     return x; 91 } 92   93 int calcg(int m) 94 { 95     int s = 0; 96     for(int k=1;k<=m;k++) if(m%k==0) 97     { 98         int x = max(rtceil(L,k),(int)ceil(pow(2,m/k/(db)D))); 99         int y = rtfloor(R,k);100         s = add(s,sum(m/k,x,y));101     }102     for(int l=2;l<=m;l++) if(m%l==0&&mu[l])103     {104         int t = 0;105         for(int k=1;k*l<=m;k++) if(m%(k*l)==0)106         {107             int _l = max((int)ceil(pow(2,m/(k*l)/(db)D)),rtceil(L,k*l));108             int _r = rtfloor(R,k*l);109             t = add(t,sum(m/k*l,_l,_r));110         }111         s = add(s,mul(t,mu[l]));112     }113     return s;114 }115  116 int work()117 {118     int s = 0;119     pre();120     for(lint m=D,p=2;p<=R;m+=D,p<<=1)121         s = add(s,mul(c[m/D],calcg(m)));122     return s;123 }124  125 int main()126 {127     scanf("%d%d%d%d",&n,&D,&L,&R);128     printf("%d\n",work());129     return 0;130 }