北京集训:20180311

于是今天又是一场愉悦的考试。

笨蒟蒻今天终于不爆零啦!好开心!

T1:

说白了就是要在区间内选出一个子集使之xor和为0。
直觉告诉我这东西线段树。
然而三种标记没法合并啊，怎么办啊......
莫队吧，区间修改不可做。
看80分的值域那么小，要不然，我们来倍增沃尔什变换吧。
不不不，这是什么鬼畜的东西......
算了，40分值域才15，n^2暴力+bitset可过。
好像能线性基?然而40分不需要线性基的，算了不管了暴力了。
然后下来发现大力线性基有80分......
说下正解:
显然当r-l+1>30的时候一定输出Yes(这不显然啊，我怎么没想出来)。
为什么?考虑线性基的插入过程，我们逐个插入，当某个数不能被插入时说明xor出0，符合要求。
而值域10^9代表线性基最多插30个，根据鸽巢原理，当你插入第31个数的时候要么无法插入，要么前面已经插入出0了。
然后我们当r-l+1<=30的时候大力计算即可。
所以我们有了完美的n^2暴力，能过80分。
剩下的20分怎么办呢?考虑用线段树维护修改。
还是老问题，这个标记没法合并。
你可以线段树强行push，显然这样是O(n^2)的，而且是大常数。
其实暴力推倒(不是这个字吧)一下是可以合并的，然而我比较蒻，不愿意推(H是不行的)。
于是我选择按位考虑，or变成数字为1的位强制是1，and变成数字为0位强制是0，xor变成区间01互换。
好的，我们可以每个节点开31个char去维护这个东西是吧......
然后就有了一个常数巨大的伪正解。
考场40分代码:

 1 #include<bits/stdc++.h>
 2 #define debug cout
 3 using namespace std;
 4 const int maxn=1e3+1e2,maxe=64,maxl=32;
 5 typedef bitset<maxe> BitSet;
 6 
 7 int in[maxn],n;
 8 BitSet prv[maxn];
 9 
10 inline BitSet trans(const BitSet &sou,const int &x) {
11     BitSet ret = sou;
12     for(int i=0;i<maxl;i++) if( sou[i] ) ret[i^x] = 1;
13     return ret;
14 }
15 
16 inline void getprv(int l,int r) {
17     prv[l] &= 0; prv[l][in[l]] = 1;
18     for(int i=l+1;i<=r;i++) prv[i] = trans(prv[i-1],in[i]) , prv[i][in[i]] = 1;
19 }
20 inline bool getans(int l,int r) {
21     if( !in[l] ) return 1;
22     for(int i=l+1;i<=r;i++) if( !in[i] || prv[i-1][in[i]] ) return 1;
23     return 0;
24 }
25 
26 inline void modify(int l,int r,int x,int o) {
27     if( o == 1 ) for(int i=l;i<=r;i++) in[i] &= x;
28     if( o == 2 ) for(int i=l;i<=r;i++) in[i] |= x;
29     if( o == 3 ) for(int i=l;i<=r;i++) in[i] ^= x;
30 }
31 
32 int main() {
33     static int q;
34     scanf("%d",&n);
35     for(int i=1;i<=n;i++) scanf("%d",in+i);
36     scanf("%d",&q);
37     for(int i=1,o,l,r,x;i<=q;i++) {
38         scanf("%d%d%d",&o,&l,&r);
39         if( !o ) {
40             getprv(l,r);
41             puts(getans(l,r)?"Yes":"No");
42         } else {
43             scanf("%d",&x);
44             modify(l,r,x,o);
45         }
46     }
47     return 0;
48 }

View Code

暴力线段树80分代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cctype>
  5 #define debug cerr
  6 using namespace std;
  7 const int maxn=1e5+1e2,maxl=32;
  8 
  9 int in[maxn],n;
 10 struct SegmentTree {
 11     int l[maxn<<2],r[maxn<<2],lson[maxn<<2],rson[maxn<<2],cnt;
 12     int lazy[maxn<<2][3]; // 0 xor , 1 and , 2 or .
 13     
 14     inline void getpe(int tpe,int &reta,int &retb) {
 15         if( tpe == 0 ) reta = 1 , retb = 2;
 16         else if( tpe == 1 ) reta = 0 , retb = 2;
 17         else if( tpe == 2 ) reta = 0 , retb = 1;
 18     }
 19     inline void apply(int pos,int val,int tpe) {
 20         if( l[pos] == r[pos] ) {
 21             if( tpe == 0 ) in[l[pos]] ^= val;
 22             if( tpe == 1 ) in[l[pos]] &= val;
 23             if( tpe == 2 ) in[l[pos]] |= val;
 24         }
 25         int ta,tb; getpe(tpe,ta,tb);
 26         if( ~lazy[pos][ta] || ~lazy[pos][tb] ) push(pos);
 27         if( !~lazy[pos][tpe] ) lazy[pos][tpe] = val;
 28         else {
 29             if( tpe == 0 ) lazy[pos][tpe] ^= val;
 30             if( tpe == 1 ) lazy[pos][tpe] &= val;
 31             if( tpe == 2 ) lazy[pos][tpe] |= val;
 32         }
 33     }
 34     inline void push(int pos) {
 35         if( l[pos] == r[pos] ) return;
 36         for(int i=0;i<3;i++)
 37             if( ~lazy[pos][i] ) {
 38                 apply(lson[pos],lazy[pos][i],i) ,
 39                 apply(rson[pos],lazy[pos][i],i) ;
 40                 lazy[pos][i] = -1;
 41             }
 42     }
 43     inline void build(int pos,int ll,int rr) {
 44         l[pos] = ll , r[pos] = rr;
 45         if( ll == rr ) return;
 46         const int mid = ( ll + rr ) >> 1;
 47         build(lson[pos]=++cnt,ll,mid) ,
 48         build(rson[pos]=++cnt,mid+1,rr) ;
 49     }
 50     inline void update(int pos,int ll,int rr,int val,int tpe) {
 51         if( ll <= l[pos] && r[pos] <= rr ) return apply(pos,val,tpe);
 52         const int mid = ( l[pos] + r[pos] ) >> 1;
 53         push(pos);
 54         if( rr <= mid ) return update(lson[pos],ll,rr,val,tpe);
 55         if( ll > mid ) return update(rson[pos],ll,rr,val,tpe);
 56         update(lson[pos],ll,rr,val,tpe) , update(rson[pos],ll,rr,val,tpe);
 57     }
 58     inline int query(int pos,int tar) {
 59         if( l[pos] == r[pos] ) return in[l[pos]];
 60         const int mid = ( l[pos] + r[pos] ) >> 1;
 61         push(pos);
 62         if( tar <= mid ) return query(lson[pos],tar);
 63         else return query(rson[pos],tar);
 64     }
 65     SegmentTree() {
 66         memset(lazy,-1,sizeof(lazy));
 67     }
 68 }segt;
 69 
 70 struct LinerBase {
 71     int dat[maxl];
 72     inline bool insert(int x) {
 73         for(int i=31;~i;i--)
 74             if( x & ( 1 << i ) ) {
 75                 if( dat[i] ) x ^= dat[i];
 76                 else {
 77                     dat[i] = x;
 78                     return 1;
 79                 }
 80             }
 81         return 0;
 82     }
 83     inline void reset() {
 84         memset(dat,0,sizeof(dat));
 85     }
 86 }lb;
 87 
 88 inline bool query(int l,int r) {
 89     if( r - l + 1 > 30 ) return 1;
 90     lb.reset();
 91     for(int i=l,q;i<=r;i++) {
 92         q = segt.query(1,i);
 93         if( !lb.insert(q) ) return 1;
 94     }
 95     return 0;
 96 }
 97 
 98 __inline char nxtchar() {
 99     return getchar();
100     static const int BS = 1 << 21;
101     static char buf[BS],*st=buf+BS,*ed=buf+BS;
102     if( st == ed ) ed = buf + fread(st=buf,1,BS,stdin);
103     return st == ed ? -1 : *st++;
104 }
105 __inline int getint() {
106     int ret = 0 , ch;
107     while( !isdigit(ch=nxtchar()) );
108     do ret=ret*10+ch-'0'; while( isdigit(ch=nxtchar()) );
109     return ret;
110 }
111 
112 
113 int main() {
114     static int m;
115     n = getint();
116     for(int i=1;i<=n;i++) in[i] = getint();
117     segt.build(segt.cnt=1,1,n);
118     m = getint();
119     for(int i=1,o,l,r,x;i<=m;i++) {
120         o = getint() , l = getint() , r = getint();
121         if( !o ) puts(query(l,r)?"Yes":"No");
122         else {
123             x = getint() , o %= 3;
124             segt.update(1,l,r,x,o);
125         }
126     }
127     return 0;
128 }

View Code

正解代码:

  1 #pragma GCC optimize(3)
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cctype>
  5 const int maxn=1e5+1e2,maxl=32;
  6 
  7 unsigned in[maxn];
  8 int n;
  9 struct SegmentTree {
 10     int l[maxn<<2],r[maxn<<2],lson[maxn<<2],rson[maxn<<2],cnt;
 11     struct Node {
 12         char dat[maxl];
 13         char& operator [] (const int &x) {
 14             return dat[x];
 15         }
 16         inline bool empty() {
 17             for(int i=0;i<maxl;i++) if( ~dat[i] ) return 0;
 18             return 1;
 19         }
 20         inline void reset() {
 21             memset(dat,-1,sizeof(dat));
 22         }
 23         inline unsigned build() {
 24             unsigned ret = 0;
 25             for(int i=0;i<maxl;i++) {
 26                 //if( !~dat[i] ) throw "You shouldn't build this ."; ???
 27                 ret |= ( (unsigned) dat[i] << i );
 28             }
 29             return ret;
 30         }
 31         inline void fill(unsigned x) {
 32             for(int i=0;i<maxl;i++) dat[i] = ( x >> i ) & 1;
 33         }
 34         Node() {
 35             memset(dat,-1,sizeof(dat));
 36         }
 37     }ns[maxn<<2],lazy[maxn<<2]; // lazy = 1 means fill 1 , lazy = 0 means fill 0 , lazy = 2 means neg , lazy = -1 means nothing to do .
 38     inline void apply(int pos,Node &sou) {
 39         for(int i=0;i<maxl;i++) if( ~sou[i] ) {
 40             if( sou[i] != 2 ) ns[pos][i] = lazy[pos][i] = sou[i];
 41             else {
 42                 ns[pos][i] ^= 1;
 43                 if( !~lazy[pos][i] ) lazy[pos][i] = 2;
 44                 else if( lazy[pos][i] == 2 ) lazy[pos][i] = -1;
 45                 else lazy[pos][i] ^= 1;
 46             }
 47         }
 48     }
 49     inline void push(int pos) {
 50         if( l[pos] == r[pos] || lazy[pos].empty() ) return;
 51         apply(lson[pos],lazy[pos]) ,
 52         apply(rson[pos],lazy[pos]) ;
 53         lazy[pos].reset();
 54     }
 55     inline void build(int pos,int ll,int rr) {
 56         l[pos] = ll , r[pos] = rr;
 57         if( ll == rr ) return ns[pos].fill(in[ll]);
 58         const int mid = ( ll + rr ) >> 1;
 59         build(lson[pos]=++cnt,ll,mid) ,
 60         build(rson[pos]=++cnt,mid+1,rr) ;
 61     }
 62     inline void update(int pos,int ll,int rr,Node &o) {
 63         if( ll <= l[pos] && r[pos] <= rr ) return apply(pos,o);
 64         const int mid = ( l[pos] + r[pos] ) >> 1;
 65         push(pos);
 66         if( rr <= mid ) return update(lson[pos],ll,rr,o);
 67         if( ll > mid ) return update(rson[pos],ll,rr,o);
 68         update(lson[pos],ll,rr,o) , update(rson[pos],ll,rr,o);
 69     }
 70     inline unsigned query(int pos,int tar) {
 71         if( l[pos] == r[pos] ) return ns[pos].build();
 72         const int mid = ( l[pos] + r[pos] ) >> 1;
 73         push(pos);
 74         if( tar <= mid ) return query(lson[pos],tar);
 75         else return query(rson[pos],tar);
 76     }
 77     SegmentTree() {
 78         memset(lazy,-1,sizeof(lazy));
 79     }
 80 }segt;
 81 
 82 struct LinerBase {
 83     unsigned dat[maxl];
 84     inline bool insert(unsigned x) {
 85         for(int i=31;~i;i--)
 86             if( x & ( 1 << i ) ) {
 87                 if( dat[i] ) x ^= dat[i];
 88                 else {
 89                     dat[i] = x;
 90                     return 1;
 91                 }
 92             }
 93         return 0;
 94     }
 95     inline void reset() {
 96         memset(dat,0,sizeof(dat));
 97     }
 98 }lb;
 99 
100 inline bool query(int l,int r) {
101     if( r - l + 1 > 30 ) return 1;
102     lb.reset();
103     for(int i=l,q;i<=r;i++) {
104         q = segt.query(1,i);
105         if( !lb.insert(q) ) return 1;
106     }
107     return 0;
108 }
109 
110 inline SegmentTree::Node getnode(const unsigned &x,const int o) {
111     SegmentTree::Node ret;
112     if( !o ) {
113         for(int i=0;i<maxl;i++) if( ( x >> i ) & 1 ) ret[i] = 2;
114     } else if( o == 1 ) {
115         for(int i=0;i<maxl;i++) if( ! ( ( x >> i ) & 1 ) ) ret[i] = 0;
116     } else if( o == 2 ) {
117         for(int i=0;i<maxl;i++) if( ( x >> i ) & 1u ) ret[i] = 1;
118     }
119     return ret;
120 }
121 
122 inline char nxtchar() {
123     static const int BS = 1 << 21;
124     static char buf[BS],*st=buf+BS,*ed=buf+BS;
125     if( st == ed ) ed = buf + fread(st=buf,1,BS,stdin);
126     return st == ed ? -1 : *st++;
127 }
128 inline int getint() {
129     int ret = 0 , ch;
130     while( !isdigit(ch=nxtchar()) );
131     do ret=ret*10+ch-'0'; while( isdigit(ch=nxtchar()) );
132     return ret;
133 }
134 
135 
136 int main() {
137     static int m;
138     static unsigned x;
139     static SegmentTree::Node ONode;
140     n = getint();
141     for(int i=1;i<=n;i++) in[i] = getint();
142     segt.build(segt.cnt=1,1,n);
143     m = getint();
144     for(int i=1,o,l,r;i<=m;i++) {
145         o = getint() , l = getint() , r = getint();
146         if( !o ) puts(query(l,r)?"Yes":"No");
147         else {
148             x = getint() , o %= 3;
149             ONode = getnode(x,o);
150             segt.update(1,l,r,ONode);
151         }
152     }
153     return 0;
154 }

View Code

T2:

首先不要被这题面吓到......
他说出现位置完全相同，好像似曾相识的样子啊，等等，这不就是后缀自动机的节点的right集合的性质吗?
所以第一个条件就是说我们不能在根节点到其他点的一条链上选出两个人。
第二个条件就是我们需要找一些链覆盖所有节点。
好的，建立广义SAM然后跑最小链覆盖不就好了。
无解什么鬼啊?怕不是炸胡，样例没有我也构造不出来，不管他了QAQ。
于是这样你就get到了30分......
为什么?显然一个人认识的人并不是在一般的一条链上，而是在从根节点到这个点的一条链。
也就是说，我们最小链覆盖的所有链都必须从根节点的后继节点开始。
这东西最小链覆盖没法做了，我们需要拆点然后跑有上下界的最小流。
最小流怎么办?首先先随便找出一条可行流，拆掉超级源超级汇和inf边，再由汇点向源点退流，减去退掉的流量就好了。
考场30分代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<map>
  6 #include<queue>
  7 #define debug cout
  8 using namespace std;
  9 const int maxn=5e3+1e2;
 10 const int inf=0x3f3f3f3f;
 11 
 12 int in[maxn],n,ans;
 13 
 14 namespace NetworkFlow {
 15     int s[maxn<<2],t[maxn<<6],nxt[maxn<<6],f[maxn<<6],dep[maxn<<2];
 16     int st,ed;
 17     inline void coredge(int from,int to,int flow) {
 18         static int cnt = 1;
 19         t[++cnt] = to , f[cnt] = flow ,
 20         nxt[cnt] = s[from] , s[from] = cnt;
 21     }
 22     inline void singledge(int from,int to,int flow) {
 23         coredge(from,to,flow) , coredge(to,from,0);
 24     }
 25     inline bool bfs() {
 26         memset(dep,-1,sizeof(dep)) , dep[st] = 0;
 27         queue<int> q; q.push(st);
 28         while( q.size() ) {
 29             const int pos = q.front(); q.pop();
 30             for(int at=s[pos];at;at=nxt[at])
 31                 if( f[at] && !~dep[t[at]] )
 32                     dep[t[at]] = dep[pos] + 1 , q.push(t[at]);
 33         }
 34         return ~dep[ed];
 35     }
 36     inline int dfs(int pos,int flow) {
 37         if( pos == ed ) return flow;
 38         int ret = 0 , now = 0;
 39         for(int at=s[pos];at;at=nxt[at])
 40             if( f[at] && dep[t[at]] > dep[pos] ) {
 41                 now = dfs(t[at],min(flow,f[at])) ,
 42                 ret += now , flow -= now ,
 43                 f[at] -= now , f[at^1] += now;
 44                 if( !flow ) return ret;
 45             }
 46         if( !ret ) dep[pos] = -1;
 47         return ret;
 48     }
 49     inline int dinic() {
 50         int ret = 0 , now = 0;
 51         while( bfs() ) {
 52             while( ( now = dfs(st,inf) ) )
 53                 ret += now;
 54         }
 55         return ret;
 56     }
 57 }
 58 
 59 namespace SAM {
 60     map<int,int> ch[maxn<<1];
 61     int fa[maxn<<1],len[maxn<<1],root,last,cnt;
 62     
 63     inline int NewNode(int ll) {
 64         len[++cnt] = ll;
 65         return cnt;
 66     }
 67     inline void extend(int x) {
 68         int p = last;
 69         int np = NewNode(len[p]+1);
 70         while( p && ch[p].find(x) == ch[p].end() ) ch[p][x] = np , p = fa[p];
 71         if( !p ) fa[np] = root;
 72         else {
 73             int q = ch[p][x];
 74             if( len[q] == len[p] + 1 ) fa[np] = q;
 75             else {
 76                 int nq = NewNode(len[p]+1);
 77                 ch[nq] = ch[q] , fa[nq] = fa[q];
 78                 fa[np] = fa[q] = nq;
 79                 while( p && ch[p][x] == q ) ch[p][x] = nq , p = fa[p];
 80             }
 81         }
 82         last = np;
 83     }
 84     inline void Ex_extend(int* sou,int li) {
 85         last = root;
 86         for(int i=1;i<=li;i++) {
 87             if( ch[last].find(sou[i]) != ch[last].end() ) last = ch[last][sou[i]];
 88             else extend(sou[i]);
 89         }
 90     }
 91 }
 92 
 93 inline void build() {
 94     using SAM::ch;using SAM::cnt;
 95     using NetworkFlow::singledge; using NetworkFlow::st; using NetworkFlow::ed;
 96     st = cnt * 2 + 1 , ed = st + 1;
 97     #define cov(x) (x+cnt)
 98     for(int i=1;i<=cnt;i++) {
 99         singledge(st,i,1) , singledge(cov(i),ed,1);
100         for(map<int,int>::iterator it=ch[i].begin();it!=ch[i].end();++it)
101             singledge(i,cov(it->second),1);
102     }
103     ans = cnt;
104 }
105 
106 int main() {
107     static int k,m;
108     SAM::root = SAM::NewNode(0);
109     scanf("%d%d",&k,&m);
110     if( k == 1 ) return puts("1"),0;
111     while(m--) {
112         scanf("%d",&n);
113         for(int i=1;i<=n;i++) scanf("%d",in+i);
114         SAM::Ex_extend(in,n);
115     }
116     build();
117     ans -= NetworkFlow::dinic();
118     printf("%d
",ans);
119     return 0;
120 }

View Code

正解代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<map>
  6 #include<queue>
  7 #define debug cout
  8 using namespace std;
  9 const int maxn=5e3+1e2;
 10 const int inf=0x3f3f3f3f;
 11  
 12 int in[maxn],n,ans,sum;
 13  
 14 namespace NetworkFlow {
 15     int s[maxn<<2],t[maxn<<6],nxt[maxn<<6],f[maxn<<6],dep[maxn<<2],deg[maxn<<2],cnt=1;
 16     int bak[maxn<<2],bcnt;
 17     int st,ed,_s,_t;
 18     inline void coredge(int from,int to,int flow) {
 19         t[++cnt] = to , f[cnt] = flow ,
 20         nxt[cnt] = s[from] , s[from] = cnt;
 21     }
 22     inline void singledge(int from,int to,int flow) {
 23         coredge(from,to,flow) , coredge(to,from,0);
 24     }
 25     inline bool bfs() {
 26         memset(dep,-1,sizeof(dep)) , dep[st] = 0;
 27         queue<int> q; q.push(st);
 28         while( q.size() ) {
 29             const int pos = q.front(); q.pop();
 30             for(int at=s[pos];at;at=nxt[at])
 31                 if( f[at] && !~dep[t[at]] ) {
 32                     dep[t[at]] = dep[pos] + 1 , q.push(t[at]);
 33                 }
 34         }
 35         return ~dep[ed];
 36     }
 37     inline int dfs(int pos,int flow) {
 38         if( pos == ed ) return flow;
 39         int ret = 0 , now = 0;
 40         for(int at=s[pos];at;at=nxt[at])
 41             if( f[at] && dep[t[at]] > dep[pos] ) {
 42                 now = dfs(t[at],min(flow,f[at])) ,
 43                 ret += now , flow -= now ,
 44                 f[at] -= now , f[at^1] += now;
 45                 if( !flow ) return ret;
 46             }
 47         if( !ret ) dep[pos] = -1;
 48         return ret;
 49     }
 50     inline int dinic() {
 51         int ret = 0 , now = 0;
 52         while( bfs() ) {
 53             while( ( now = dfs(st,inf) ) )
 54                 ret += now;
 55         }
 56         return ret;
 57     }
 58     inline int findflow() {
 59         for(int at=s[_t];at;at=nxt[at])
 60             if( t[at] = _s ) return f[at^1];
 61         throw "It shouldn't be here";
 62     }
 63     inline void backup() {
 64         memcpy(bak,s,sizeof(s)) , bcnt = cnt;
 65     }
 66     inline void restore() {
 67         memcpy(s,bak,sizeof(bak)) , cnt = bcnt;
 68     }
 69 }
 70  
 71 namespace SAM {
 72     map<int,int> ch[maxn<<1];
 73     int fa[maxn<<1],len[maxn<<1],root,last,cnt;
 74      
 75     inline int NewNode(int ll) {
 76         len[++cnt] = ll;
 77         return cnt;
 78     }
 79     inline void extend(int x) {
 80         int p = last;
 81         int np = NewNode(len[p]+1);
 82         while( p && ch[p].find(x) == ch[p].end() ) ch[p][x] = np , p = fa[p];
 83         if( !p ) fa[np] = root;
 84         else {
 85             int q = ch[p][x];
 86             if( len[q] == len[p] + 1 ) fa[np] = q;
 87             else {
 88                 int nq = NewNode(len[p]+1);
 89                 ch[nq] = ch[q] , fa[nq] = fa[q];
 90                 fa[np] = fa[q] = nq;
 91                 while( p && ch[p][x] == q ) ch[p][x] = nq , p = fa[p];
 92             }
 93         }
 94         last = np;
 95     }
 96     inline void Ex_extend(int* sou,int li) {
 97         last = root;
 98         for(int i=1;i<=li;i++) {
 99             if( ch[last].find(sou[i]) != ch[last].end() ) last = ch[last][sou[i]];
100             else extend(sou[i]);
101         }
102     }
103 }
104  
105 inline void build() {
106     using SAM::ch;using SAM::cnt;
107     using namespace NetworkFlow;
108     _s = cnt * 2 + 1 , _t = _s + 1 , st = _t + 1 , ed = st + 1;
109     #define cov(x) (x+cnt)
110     for(int i=1;i<=cnt;i++) {
111         if( i != 1 ) ++deg[i] , --deg[cov(i)];
112         for(map<int,int>::iterator it=ch[i].begin();it!=ch[i].end();it++) {
113             const int tar = it->second;
114             if( i == 1 ) singledge(_s,tar,1);
115             else singledge(cov(i),tar,1);
116         }
117         if( i != 1 ) singledge(cov(i),_t,1);
118     }
119     backup();
120     for(int i=1;i<=_t;i++) {
121         if( !deg[i] ) continue;
122         if( deg[i] > 0 ) singledge(i,ed,deg[i]) , sum += deg[i];
123         else singledge(st,i,-deg[i]);
124     }
125     singledge(_t,_s,inf);
126 }
127 inline int getans() {
128     using namespace NetworkFlow;
129     int d = dinic();
130     if( d != sum ) return 0; // No solution .
131     int ret = findflow();
132     restore();
133     st = _t , ed = _s;
134     int dd = dinic();
135     return ret - dd;
136 }
137 
138 int main() {
139     static int k,m;
140     SAM::root = SAM::NewNode(0);
141     scanf("%d%d",&k,&m);
142     if( k == 1 ) return puts("1"),0;
143     while(m--) {
144         scanf("%d",&n);
145         for(int i=1;i<=n;i++) scanf("%d",in+i);
146         SAM::Ex_extend(in,n);
147     }
148     build();
149     ans = getans();
150     printf("%d
",ans);
151     return 0;
152 }

View Code

T3:

人生第一道交互题啊......
一看又是神仙题，好的，既然算出一个多项式有40%的分，那我钦定m为0，扔掉b，让他帮我插值，我直接NTT求解A好了。
什么?他没告诉我原根?好吧，我自己求。
求原根这种东西，反正就是把p-1先分解质因数，然后保证x^(p/div[i])在mod p意义下不为1就行了。
原根不能很大，暴力一个一个找就可以通过的说。
(一下为吐槽时间)
然后写了，调了，WA样例了......检查NTT，没错......输出插值用的x，没错......
自行插值他给的多项式，等等，怎么我计算出的值和他算出的不一样啊?
怕不是交互库WA了，去看通知，10:54有一个修正......
赶紧下载下来看看，woc怎么还是WA的?
改用单点插值看看，好，对了。
交互库WA了什么的，这是天不让我做题啊。
好的，单点插值交吧，反正大家都没法做就是了。
11:04,再次修正，这次交互库终于对了......
(吐槽时间结束)
官方题解放上来吧，真·神仙打架(蒟蒻只能瑟瑟发抖):

考场31分代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include"poly.h"
 6 //#define fixed
 7 typedef long long int lli;
 8 using namespace std;
 9 const int maxn=65539;
10 
11 int mod,g,len,n;
12 lli ans[maxn],tp[maxn];
13 int oty[maxn];
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 void NTT(lli* dst,int n,int ope) {
24     for(int i=0,j=0;i<n;i++) {
25         if( i < j ) swap( dst[i] , dst[j] );
26         for(int t=n>>1;(j^=t)<t;t>>=1) ;
27     }
28     for(int len=2;len<=n;len<<=1) {
29         const int h = len >> 1;
30         lli per = fastpow(g,mod/(len));
31         if( !~ope ) per = fastpow(per,mod-2);
32         for(int st=0;st<n;st+=len) {
33             lli w = 1;
34             for(int pos=0;pos<h;pos++) {
35                 const lli u = dst[st+pos] , v = dst[st+pos+h] * w % mod;
36                 dst[st+pos] = ( u + v ) % mod ,
37                 dst[st+pos+h] = ( u - v + mod ) % mod ,
38                 w = w * per % mod;
39             }
40         }
41     }
42     if( !~ope ) {
43         const lli mul = fastpow(n,mod-2);
44         for(int i=0;i<n;i++) dst[i] = dst[i] * mul % mod;
45     }
46 }
47 
48 namespace FindRoot {
49     int divs[maxn],cnt;
50     inline void cut(int x) {
51         for(int i=2;(lli)i*i<=x;i++)
52             if( ! ( x % i ) ) {
53                 divs[++cnt] = i;
54                 while( ! ( x % i ) ) x /= i;
55             }
56     }
57     inline bool judge(int x) {
58         for(int i=1;i<=cnt;i++)
59             if( fastpow(x,mod/divs[i]) == 1 ) return 0;
60         return 1;
61     }
62     inline int findrt() {
63         cut(mod-1);
64         for(int i=2;i<mod;i++) if( judge(i) ) return i;
65         throw "There is no primary root ! ";
66     }
67 }
68 
69 int init(int l,int r,int _n,int P) {
70     ++_n;
71     for(len=1;len<=_n;len<<=1) ;
72     mod = P , n = _n , g = FindRoot::findrt();
73     return 0;
74 }
75 void solve(int *A,int *B) {
76     for(int i=0;i<len;i++) tp[i] = fastpow(g,(mod/len)*i);
77     //#ifdef fixed
78         for(int i=len;i;i--) tp[i] = tp[i-1];
79         get(len,tp,oty);
80         for(int i=0;i<len;i++) ans[i] = oty[i+1];
81     /*#else
82         for(int i=0;i<len;i++) ans[i] = get(tp[i]);
83     #endif*/
84     NTT(ans,len,-1);
85     for(int i=0;i<n;i++) A[i] = B[i] = ans[i];
86 }

View Code

某不科学的超(时)std(卡评测8分钟的说):

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define rep(i,a,b) for (int i = a, _ = b; i <= _; i ++)
  4 #define per(i,a,b) for (int i = a, _ = b; i >= _; i --)
  5 #define For(i,a,b) for (int i = a, _ = b; i <  _; i ++)
  6  
  7 #include <ext/pb_ds/assoc_container.hpp>
  8 #include <ext/pb_ds/hash_policy.hpp>
  9  
 10 #include "poly.h"
 11  
 12 typedef long long ll;
 13  
 14 int mod, g;
 15  
 16 namespace Interpolation {
 17  
 18 #define iter(i, n) for (int i = 1; i <= n; ++i)
 19 #define iter0(i, n) for (int i = 0; i < n; ++i)
 20 #define forw(i, a, b) for (int i = a; i <= b; ++i)
 21 #define down(i, a, b) for (int i = b; i >= a; --i)
 22  
 23 #define reset(a, l, r) forw(i, l, r) a[i] = 0;
 24 #define NR 401000
 25  
 26   typedef vector<int> Poly;
 27  
 28   inline int pr(int a, int z) {
 29     int s = 1;
 30     while (z > 0) {
 31       if (z % 2 == 1) s = 1ll * s * a % mod;
 32       a = 1ll * a * a % mod;
 33       z /= 2;
 34     }
 35     return s;
 36   }
 37  
 38   inline int mod_inv(int a) { return pr(a, mod - 2); }
 39  
 40   void fft(int *a, int n, int ty) {
 41     for (int i = n >> 1, j = 1, k; j < n - 1; ++j) {
 42       if (i > j) swap(a[i], a[j]);
 43       for (k = n >> 1; k <= i; k >>= 1) i ^= k;
 44       i ^= k;
 45     }
 46  
 47     for (int m = 2; m <= n; m <<= 1) {
 48       int h = m >> 1, wm = pr(g, (mod - 1) / m * (ty == +1 ? 1 : (m - 1)));
 49  
 50       for (register int i = 0; i < n; i += m) {
 51     register int w = 1;
 52     for (int j = i; j < i + h; ++j) {
 53       register int u = a[j], v = 1ll * w * a[j + h] % mod;
 54                      
 55       a[j] = (u + v) % mod;
 56       a[j + h] = (u - v + mod) % mod;
 57       w = 1ll * w * wm % mod;
 58     }
 59       }
 60     }
 61  
 62     if (ty == -1) {
 63       int iv = mod_inv(n);
 64       iter0(i, n) a[i] = 1ll * a[i] * iv % mod;
 65     }
 66   }
 67  
 68   ostream& operator<<(ostream &output, const Poly &a){  
 69     output << "[";
 70     int la = a.size();
 71     iter0(i, la)
 72       output << a[i] << (i + 1 == la ? ']' : ',');
 73     return output;
 74   }
 75  
 76   void upd(Poly &a) { while (!a.empty() && a.back() == 0) a.pop_back(); }
 77  
 78   inline Poly operator+(const Poly &a, const Poly &b) {
 79     int la = a.size(), lb = b.size();
 80     int lc = max(la, lb);
 81     Poly c(lc);
 82     iter0(i, lc) c[i] = ((i < la ? a[i] : 0) + (i < lb ? b[i] : 0)) % mod;
 83     return upd(c), c;
 84   }
 85   inline void poly_multo(int a[], int b[], int N) {
 86     fft(a, N, +1), fft(b, N, +1);
 87     iter0(i, N) a[i] = 1ll * a[i] * b[i] % mod;
 88     fft(a, N, -1);
 89   }
 90  
 91   int ta[NR], tb[NR];
 92  
 93   Poly operator*(const Poly &a, const Poly &b) {
 94     int la = a.size(), lb = b.size();
 95          
 96     Poly c(la + lb - 1);
 97          
 98     if (la + lb <= 100) {
 99       iter0(i, la) iter0(j, lb) c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % mod;
100     } else {
101       int N;
102       for (N = 1; N < la + lb; N <<= 1);
103       iter0(i, N) {
104     ta[i] = (i < la ? a[i] : 0);
105     tb[i] = (i < lb ? b[i] : 0);
106       }
107       poly_multo(ta, tb, N);
108       iter0(i, la + lb - 1) c[i] = ta[i];
109     }
110     return upd(c), c;
111   }
112   int ccc = 0;
113   int ti[NR];
114  
115   void poly_inv(int *f, int *inv, int n) {
116     if (n == 0) {
117       inv[0] = mod_inv(f[0]);
118       return;
119     }
120     poly_inv(f, inv, n / 2);
121     static int t[140000];
122     int N = 1;
123     for (; N <= n * 2; N <<= 1);
124     iter0(i, N) t[i] = i <= n ? f[i] : 0; reset(inv, n / 2 + 1, N);
125     fft(inv, N, +1); fft(t, N, +1);
126     iter0(i, N) inv[i] = (2 + mod - 1ll * inv[i] * t[i] % mod) * inv[i] % mod;
127     fft(inv, N, -1);
128   }
129  
130   void poly_mod(int *a, int *b, int *c, int n, int m) {
131     if (n < m) {
132       iter0(i, m) c[i] = i <= n ? a[i] : 0;
133       return;
134     }
135     static int f[140000], g[140000];
136     if (n < 100) {
137       int invb = mod_inv(b[m]);
138       memcpy(f, a, sizeof(int) * (n + 1));
139       down(i, n, m) {
140     int t = 1ll * f[i] * invb % mod;
141     forw(j, 0, m) (f[i - j] += mod - 1ll * t * b[m - j] % mod) %= mod;
142       }
143       memcpy(c, f, sizeof(int) * m);
144       return;
145     }
146          
147     int N;
148     for (N = 1; N <= max(n, 2 * (n - m)) + 10; N <<= 1);
149     reset(g, 0, N);
150          
151     forw(i, 0, n - m) f[i] = i <= m ? b[m - i] : 0; reset(f, n - m + 1, N);
152     poly_inv(f, g, n - m); reset(g, n - m + 1, N);
153     forw(i, 0, n - m) f[i] = a[n - i];
154     poly_multo(g, f, N);
155     reset(g, n - m + 1, N);
156     reverse(g, g + n - m + 1);
157     forw(i, 0, m) f[i] = b[i]; reset(f, m + 1, N);
158     poly_multo(f, g, N);
159     iter0(i, m) c[i] = (a[i] + mod - f[i]) % mod;
160   }
161   int tr[NR];
162  
163   Poly operator%(const Poly &a, const Poly &b) {
164          
165     int la = a.size(), lb = b.size(), N;
166     Poly c(lb);
167     for (N = 1; N < la + lb; N <<= 1);
168     iter0(i, N) {
169       ta[i] = (i < la ? a[i] : 0);
170       tb[i] = (i < lb ? b[i] : 0);
171     }
172     poly_mod(ta, tb, tr, la - 1, lb - 1);
173          
174     iter0(i, lb) c[i] = tr[i];
175     iter0(i, N) tr[i] = 0;
176     upd(c);
177          
178     return c;
179   }
180   Poly t[NR], tt[NR];
181   int tsz, lc[NR], rc[NR];
182  
183  
184   void init(int &x, int l, int r, int *a) {
185     x = ++tsz;
186     if (l == r) {
187       t[x] = { (mod - a[l]) % mod, 1 };
188       return;
189     }
190     int mid = (l + r) / 2;
191     init(lc[x], l, mid, a);
192     init(rc[x], mid + 1, r, a);
193     t[x] = t[lc[x]] * t[rc[x]];
194   }
195  
196   int eval(const Poly &A, int x) {
197     int p = 1, res = 0;
198     for (auto it = A.begin(); it != A.end(); ++it) {
199       res = (res + 1ll * p * *it) % mod;
200       p = 1ll * p * x % mod;
201     }
202     return res;
203   }
204  
205   int pp[NR];
206  
207   Poly D(const Poly &a) {
208     int la = a.size();
209     Poly c(la - 1);
210     iter(i, la - 1) c[i - 1] = 1ll * i * a[i] % mod;
211     return c;
212   }
213  
214   void s2(int x, int l, int r, const Poly &f, int qX[], int ans[]) {
215     if (f.size() < 1000 || r - l + 1 <= 200) {
216       forw(i, l, r) pp[i] = 1;
217       for (auto it = f.begin(); it != f.end(); ++it) {
218     forw(i, l, r) {
219       ans[i] = (ans[i] + 1ll * pp[i] * *it) % mod;
220       pp[i] = 1ll * pp[i] * qX[i] % mod;
221     }
222       }
223       return;
224     }
225  
226     int mid = (l + r) / 2;
227     s2(lc[x], l, mid, f % t[lc[x]], qX, ans);
228     s2(rc[x], mid + 1, r, f % t[rc[x]], qX, ans);
229   }
230   int root;
231  
232  
233  
234   void evaluation(const Poly &f, bool inited, int qX[], int ans[], int m) {
235     if (!inited) {
236       tsz = 0;
237       init(root, 1, m, qX);
238     }
239     s2(root, 1, m, f, qX, ans);
240          
241   }
242  
243   int px[NR], py[NR], qx[NR], qy[NR], Q[NR], n, m;
244  
245   Poly s1(int x, int l, int r) {
246     if (l == r) {
247       Poly tmp = { (int) (1ll * py[l] * mod_inv(Q[l]) % mod) };
248       return tmp;
249     }
250     int mid = (l + r) / 2;
251     Poly L = s1(lc[x], l, mid), R = s1(rc[x], mid + 1, r);
252     return L * t[rc[x]] + R * t[lc[x]];
253   }
254  
255   Poly interpolation(int m, long long *x, int *y) {
256     n = m;
257     for (int i = 1; i <= n; i ++)
258       px[i] = x[i] % mod, py[i] = y[i];
259     init(root, 1, n, px);
260     evaluation(D(t[1]), true, px, Q, n);
261     return s1(root, 1, n);
262   }
263  
264 }
265  
266 inline int rnd() {
267   if (RAND_MAX < mod)
268     return rand() << 15 | rand();
269   else
270     return rand();
271 }
272  
273 inline int Pow(ll a, ll b, int p = mod) {
274   int t = 1;
275   //b %= p - 1;
276   a %= p;
277   while (b) {
278     if (b & 1) t = 1ll * t * a % p;
279     a = 1ll * a * a % p, b >>= 1;
280   }
281   return t;
282 }
283    
284 inline bool check(int x, int k) {
285   return (mod - 1) % k == 0 && k != mod - 1 && Pow(x, k) == 1;
286 }
287  
288 inline int get_root() {
289   for (int r = 2;; r ++) {
290     int flag = 1;
291     for (int k = 1; 1ll * k * k <= mod; k ++) {
292       if (check(r, k) || check(r, (mod - 1) / k)) {
293     flag = 0;
294     break;
295       }
296     }
297     if (flag) return r;
298   }
299 }
300  
301 inline int get_log(int a, int x) {
302   static __gnu_pbds::gp_hash_table<int, int> ms;
303   ms.clear();
304   int m = int(sqrt(mod) + 0.5);
305   int t = 1, xx = Pow(a, m);
306   rep (i , 0 , mod / m + 1) {
307     if (ms.find(t) == ms.end()) ms[t] = i;
308     t = 1ll * t * xx % mod;
309   }
310   //cerr << ms.size() << endl;
311   t = Pow(a, mod - 2);
312   //assert(1ll * a * t % mod == 1);
313   rep (i , 0 , m) {
314     if (ms.find(x) != ms.end())
315       return ms[x] * m + i;
316     x = 1ll * x * t % mod;
317   }
318   assert(0);
319   return -1;
320 }
321  
322 const int maxn = 100007;
323  
324 int n, m;
325 ll x[maxn];
326 int y[maxn];
327  
328 int init(int l, int r, int _n, int P) {
329   //auto st = clock();
330   srand(time(0));
331   n = _n;
332   mod = P;
333   g = get_root();
334   for (;;) {
335     m = rnd() % (r - l + 1) + l;
336     int z = get_log(g, m);
337     if (z & 1) {
338       //cerr << "init time: " << (clock() - st) / 1000.0 << endl;
339       return m;
340     }
341   }
342 }
343  
344 void solve(int *A, int *B) {
345   //auto st = clock();
346  
347   int k2 = 1, k1 = mod - 1;
348   while (k1 % 2 == 0) k1 >>= 1, k2 <<= 1;
349   int N = n + 1 + (((n + 1) & 1) ^ 1);
350   int a = get_log(g, m), c = N % (mod - 1);
351   assert(Pow(g, a) == m);
352   int _a = Pow(a % k2, k2 / 2 - 1, k2);
353   assert(1ll * _a * a % k2 == 1);
354   for (int d = 1, i = 1; i <= n + N + 1; d += 2, i ++) {
355     int b = 1ll * c * d % k2 * _a % k2;
356     //int _d = Pow(g, 1ll * d * k1);
357     ll _d = 1ll * d * k1;
358     ll _b = 1ll * b * k1 % mod;
359     assert(1ll * a * _b % (k1 * k2) == 1ll * c * _d % (k1 * k2));
360     _d = Pow(g, _d);
361     x[i] = 1ll * _b * mod - 1ll * _d * (mod - 1);
362     if (x[i] < 0) x[i] += 1ll * mod * (mod - 1);
363     assert(x[i] % mod == _d);
364     assert(x[i] % (mod - 1) == _b);
365     assert(Pow(x[i], N) == Pow(m, x[i]));
366   }
367    
368   //cerr << "get x time: " << (clock() - st) / 1000.0 << endl;
369  
370   //st = clock();
371   get(n + N + 1, x, y);
372   //get(n, x, y);
373   //get(N + 1, x + n, y + n);
374   //cerr << "get y time: " << (clock() - st) / 1000.0 << endl;
375  
376   //st = clock();
377   auto F = Interpolation::interpolation(n + N + 1, x, y);
378   //cerr << "get F time: " << (clock() - st) / 1000.0 << endl;
379  
380   rep (i , 0 , n) A[i] = F[i];
381   rep (i , N , N + n) B[i - N] = F[i];
382 }

View Code

交互库:

  1 #include <bits/stdc++.h>
  2 
  3 #include "poly.h"
  4 
  5 using namespace std;
  6 
  7 #define ER_TOKEN "WA"
  8 #define WA_TOKEN "WA"
  9 #define HF_TOKEN "HF"
 10 #define AC_TOKEN "AC"
 11 #define ED_TOKEN "ED"
 12 
 13 inline static void halt(int value = 0)
 14 {
 15     printf(ED_TOKEN);
 16     exit(value);
 17 }
 18 
 19 namespace Variants {
 20 
 21     const char fin [] = "poly.in";
 22     const char fout[] = "poly.out";
 23 
 24     const int maxN = 100000 + 7;
 25 
 26     static int mod = 998244353, g = 3;
 27 
 28     static int n, L, R, m;
 29     static int A[maxN], B[maxN], resA[maxN], resB[maxN];
 30 
 31     inline static int Pow(int a, long long b)
 32     {
 33         int t = 1;
 34         for (/*b %= mod - 1*/; b; b >>= 1, a = 1ll * a * a % mod)
 35             if (b & 1)
 36                 t = 1ll * t * a % mod;
 37         return t;
 38     }
 39 
 40     inline static bool check(int x, int k)
 41     {
 42         return (mod - 1) % k == 0 && k != mod - 1 && Pow(x, k) == 1;
 43     }
 44 
 45     inline static void get_root()
 46     {
 47         for (g = 2;; g ++)
 48         {
 49             int flag = 1;
 50             for (int k = 1; 1ll * k * k <= mod; k ++)
 51                 if (check(g, k) || check(g, (mod - 1) / k))
 52                 {
 53                     flag = 0;
 54                     break;
 55                 }
 56             if (flag)
 57                 return;
 58         }
 59     }
 60 
 61     inline static void check(long long x)
 62     {
 63         static map<int, int> ms1, ms2;
 64 
 65         if (ms1[x % mod])
 66         {
 67             puts(ER_TOKEN);
 68             printf("%d mod P exists twice.
", int(x % mod));
 69             halt(1);
 70         }
 71         ms1[x % mod] = 1;
 72         if (ms2[x % (mod - 1)])
 73         {
 74             puts(ER_TOKEN);
 75             printf("%d mod P-1 exists twice.
", int(x % (mod-1)));
 76             halt(1);
 77         }
 78         ms2[x % (mod - 1)] = 1;
 79     }
 80 
 81 }
 82 
 83 using namespace Variants;
 84 
 85 namespace Interpol {
 86 
 87     #define iter(i, n) for (int i = 1; i <= n; ++i)
 88     #define iter0(i, n) for (int i = 0; i < n; ++i)
 89     #define forw(i, a, b) for (int i = a; i <= b; ++i)
 90     #define down(i, a, b) for (int i = b; i >= a; --i)
 91 
 92     #define reset(a, l, r) forw(i, l, r) a[i] = 0;
 93     #define NR 401000
 94 
 95     typedef vector<int> Poly;
 96 
 97     inline int pr(int a, int z) {
 98         int s = 1;
 99         while (z > 0) {
100             if (z % 2 == 1) s = 1ll * s * a % mod;
101             a = 1ll * a * a % mod;
102             z /= 2;
103         }
104         return s;
105     }
106 
107     inline int mod_inv(int a) { return pr(a, mod - 2); }
108 
109     void fft(int *a, int n, int ty) {
110         for (int i = n >> 1, j = 1, k; j < n - 1; ++j) {
111             if (i > j) swap(a[i], a[j]);
112             for (k = n >> 1; k <= i; k >>= 1) i ^= k;
113             i ^= k;
114         }
115 
116         for (int m = 2; m <= n; m <<= 1) {
117             int h = m >> 1, wm = pr(g, (mod - 1) / m * (ty == +1 ? 1 : (m - 1)));
118 
119             for (register int i = 0; i < n; i += m) {
120                 register int w = 1;
121                 for (int j = i; j < i + h; ++j) {
122                     register int u = a[j], v = 1ll * w * a[j + h] % mod;
123                     
124                     a[j] = (u + v) % mod;
125                     a[j + h] = (u - v + mod) % mod;
126                     w = 1ll * w * wm % mod;
127                 }
128             }
129         }
130 
131         if (ty == -1) {
132             int iv = mod_inv(n);
133             iter0(i, n) a[i] = 1ll * a[i] * iv % mod;
134         }
135     }
136 
137     ostream& operator<<(ostream &output, const Poly &a){  
138         output << "[";
139         int la = a.size();
140         iter0(i, la)
141             output << a[i] << (i + 1 == la ? ']' : ',');
142         return output;
143     }
144 
145     void upd(Poly &a) { while (!a.empty() && a.back() == 0) a.pop_back(); }
146 
147     inline Poly operator+(const Poly &a, const Poly &b) {
148         int la = a.size(), lb = b.size();
149         int lc = max(la, lb);
150         Poly c(lc);
151         iter0(i, lc) c[i] = ((i < la ? a[i] : 0) + (i < lb ? b[i] : 0)) % mod;
152         return upd(c), c;
153     }
154     inline void poly_multo(int a[], int b[], int N) {
155         fft(a, N, +1), fft(b, N, +1);
156         iter0(i, N) a[i] = 1ll * a[i] * b[i] % mod;
157         fft(a, N, -1);
158     }
159 
160     int ta[NR], tb[NR];
161 
162     Poly operator*(const Poly &a, const Poly &b) {
163         int la = a.size(), lb = b.size();
164         
165         Poly c(la + lb - 1);
166         
167         if (la + lb <= 100) {
168             iter0(i, la) iter0(j, lb) c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % mod;
169         } else {
170             int N;
171             for (N = 1; N < la + lb; N <<= 1);
172             iter0(i, N) {
173                 ta[i] = (i < la ? a[i] : 0);
174                 tb[i] = (i < lb ? b[i] : 0);
175             }
176             poly_multo(ta, tb, N);
177             iter0(i, la + lb - 1) c[i] = ta[i];
178         }
179         return upd(c), c;
180     }
181     int ccc = 0;
182     int ti[NR];
183 
184     void poly_inv(int *f, int *inv, int n) {
185         if (n == 0) {
186             inv[0] = mod_inv(f[0]);
187             return;
188         }
189         poly_inv(f, inv, n / 2);
190         static int t[140000];
191         int N = 1;
192         for (; N <= n * 2; N <<= 1);
193         iter0(i, N) t[i] = i <= n ? f[i] : 0; reset(inv, n / 2 + 1, N);
194         fft(inv, N, +1); fft(t, N, +1);
195         iter0(i, N) inv[i] = (2 + mod - 1ll * inv[i] * t[i] % mod) * inv[i] % mod;
196         fft(inv, N, -1);
197     }
198 
199     void poly_mod(int *a, int *b, int *c, int n, int m) {
200         if (n < m) {
201             iter0(i, m) c[i] = i <= n ? a[i] : 0;
202             return;
203         }
204         static int f[140000], g[140000];
205         if (n < 100) {
206             int invb = mod_inv(b[m]);
207             memcpy(f, a, sizeof(int) * (n + 1));
208             down(i, n, m) {
209                 int t = 1ll * f[i] * invb % mod;
210                 forw(j, 0, m) (f[i - j] += mod - 1ll * t * b[m - j] % mod) %= mod;
211             }
212             memcpy(c, f, sizeof(int) * m);
213             return;
214         }
215         
216         int N;
217         for (N = 1; N <= max(n, 2 * (n - m)) + 10; N <<= 1);
218         reset(g, 0, N);
219         
220         forw(i, 0, n - m) f[i] = i <= m ? b[m - i] : 0; reset(f, n - m + 1, N);
221         poly_inv(f, g, n - m); reset(g, n - m + 1, N);
222         forw(i, 0, n - m) f[i] = a[n - i];
223         poly_multo(g, f, N);
224         reset(g, n - m + 1, N);
225         reverse(g, g + n - m + 1);
226         forw(i, 0, m) f[i] = b[i]; reset(f, m + 1, N);
227         poly_multo(f, g, N);
228         iter0(i, m) c[i] = (a[i] + mod - f[i]) % mod;
229     }
230     int tr[NR];
231 
232     Poly operator%(const Poly &a, const Poly &b) {
233         
234         int la = a.size(), lb = b.size(), N;
235         Poly c(lb);
236         for (N = 1; N < la + lb; N <<= 1);
237         iter0(i, N) {
238             ta[i] = (i < la ? a[i] : 0);
239             tb[i] = (i < lb ? b[i] : 0);
240         }
241         poly_mod(ta, tb, tr, la - 1, lb - 1);
242         
243         iter0(i, lb) c[i] = tr[i];
244         iter0(i, N) tr[i] = 0;
245         upd(c);
246         
247         return c;
248     }
249     Poly t[NR], tt[NR];
250     int tsz, lc[NR], rc[NR];
251 
252 
253     void init(int &x, int l, int r, int *a) {
254         x = ++tsz;
255         if (l == r) {
256             t[x] = { (mod - a[l]) % mod, 1 };
257             return;
258         }
259         int mid = (l + r) / 2;
260         init(lc[x], l, mid, a);
261         init(rc[x], mid + 1, r, a);
262         t[x] = t[lc[x]] * t[rc[x]];
263     }
264 
265     int eval(const Poly &A, int x) {
266         int p = 1, res = 0;
267         for (auto it = A.begin(); it != A.end(); ++it) {
268             res = (res + 1ll * p * *it) % mod;
269             p = 1ll * p * x % mod;
270         }
271         return res;
272     }
273 
274     int pp[NR];
275 
276     Poly D(const Poly &a) {
277         int la = a.size();
278         Poly c(la - 1);
279         iter(i, la - 1) c[i - 1] = 1ll * i * a[i] % mod;
280         return c;
281     }
282 
283     void s2(int x, int l, int r, const Poly &f, int qX[], int ans[]) {
284         if (f.size() < 1000 || r - l + 1 <= 200) {
285             forw(i, l, r) pp[i] = 1;
286             for (auto it = f.begin(); it != f.end(); ++it) {
287                 forw(i, l, r) {
288                     ans[i] = (ans[i] + 1ll * pp[i] * *it) % mod;
289                     pp[i] = 1ll * pp[i] * qX[i] % mod;
290                 }
291             }
292             return;
293         }
294 
295         int mid = (l + r) / 2;
296         s2(lc[x], l, mid, f % t[lc[x]], qX, ans);
297         s2(rc[x], mid + 1, r, f % t[rc[x]], qX, ans);
298     }
299     int root;
300 
301     void evaluation(const Poly &f, bool inited, int qX[], int ans[], int m) {
302         if (!inited) {
303             tsz = 0;
304             init(root, 1, m, qX);
305         }
306         s2(root, 1, m, f, qX, ans);
307         
308     }
309 
310     int px[NR], py[NR], qx[NR], qy[NR], Q[NR], n, m;
311 
312     Poly s1(int x, int l, int r) {
313         if (l == r) {
314             Poly tmp = { (int) (1ll * py[l] * mod_inv(Q[l]) % mod) };
315             return tmp;
316         }
317         int mid = (l + r) / 2;
318         Poly L = s1(lc[x], l, mid), R = s1(rc[x], mid + 1, r);
319         return L * t[rc[x]] + R * t[lc[x]];
320     }
321 
322 }
323 
324 int get(long long x)
325 {
326     check(x);
327     int res = 0, t = 1, m = Pow(Variants::m, x);
328     x %= mod;
329     for (int i = 0; i <= n; i ++)
330         {
331             (res += (1ll * m * B[i] % mod + A[i]) * t % mod) %= mod;
332             t = 1ll * t * x % mod;
333         }
334     return res;
335 }
336 
337 void get(int m, long long *X, int *Y)
338 {
339     static int x[maxN], ya[maxN], yb[maxN];
340 
341     //auto st = clock();
342 
343     for (int i = 1; i <= m; i ++)
344     {
345         check(X[i]);
346         x[i] = X[i] % mod;
347     }
348 
349     Interpol::Poly a;
350     a.resize(n + 1);
351 
352     for (int i = 0; i <= n; i ++)
353         a[i] = A[i];
354     Interpol::evaluation(a, false, x, ya, m);
355 
356     for (int i = 0; i <= n; i ++)
357         a[i] = B[i];
358     Interpol::evaluation(a, false, x, yb, m);
359 
360     //cerr << "evaluate time: " << (clock() - st) / 1000.0 << endl;
361 
362     //st = clock();
363     for (int i = 1; i <= m; i ++)
364         Y[i] = (1ll * Pow(Variants::m, X[i]) * yb[i] % mod + ya[i]) % mod;
365     //cerr << "get Y[] time: " << (clock() - st) / 1000.0 << endl;
366 }
367 
368 int main()
369 {
370     using namespace Variants;
371     freopen(fin , "r", stdin);
372     freopen(fout, "w", stdout);
373     
374     scanf("%d%d%d%d", &n, &L, &R, &mod);
375     for (int i = 0; i <= n; i ++)
376         scanf("%d", &A[i]);
377     for (int i = 0; i <= n; i ++)
378         scanf("%d", &B[i]);
379     get_root();
380 
381     m = init(L, R, n, mod);
382     if (!(L <= m && m <= R))
383     {
384         puts(WA_TOKEN);
385         printf("m=%d is not in [%d,%d]
", m, L, R);
386         return 1;
387     }
388     solve(resA, resB);
389 
390     int cntA = 0, cntB = 0;
391     for (int i = 0; i <= n; i ++)
392     {
393         cntA += (A[i] != resA[i] % mod);
394         cntB += (B[i] != resB[i] % mod);
395     }
396 
397 /*
398     for (int i = 0; i <= n; i ++)
399         cerr << resA[i] << " "; cerr << endl;
400     for (int i = 0; i <= n; i ++)
401         cerr << resB[i] << " "; cerr << endl;
402 */
403 
404     if (cntA == 0 && cntB == 0)
405         puts(AC_TOKEN);
406     else if (cntA == 0 || cntB == 0)
407     {
408         puts(HF_TOKEN);
409         char c = cntA ? 'B' : 'A';
410         printf("You answer polynomial %c correctly, the other one has %d different coefficients.
", c, cntA + cntB);
411         halt(1);
412     }
413     else
414     {
415         puts(WA_TOKEN);
416         printf("Your polynomial A and B has %d and %d different coefficients.
", cntA, cntB);
417         halt(1);
418     }
419 
420     halt();
421     return 0;
422 }

View Code

在大佬们看来的水题我才考这么几分，果然还是我太菜了呀。