The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest

https://www.jisuanke.com/contest/3098?view=challenges

优质题解

https://acm.ecnu.edu.cn/wiki/index.php?title=2019_ICPC_China_Nanchang_Invitational_Programming_Contest

A. Attack

斯坦纳树

之后再补

B. Polynomial

若干个n次函数相加 f(0)+f(1)+...+f(k)

自然数幂和 a_{d} * ( sum of i^d ) d+1次函数

max of d = n 即为n+1次函数

自然数幂和见 https://www.cnblogs.com/cmyg/p/11256321.html

510ms

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=9999991;
 14 const int maxn=1e3+10;
 15 const int maxlen=mod+10;
 16 
 17 /**
 18 1.1~9999991 inv
 19 2.use int
 20 **/
 21 
 22 /**
 23 better way:
 24 多项式快速插值
 25 luogo5158
 26 **/
 27 
 28 ll y[maxn],n;
 29 int jie[maxlen],inv_jie[maxlen],inv_num[maxlen];
 30 //ll maxv=1e3;
 31 ll maxv=mod-1;
 32 
 33 ll mul(ll a,ll b)
 34 {
 35     ll y=1;
 36     while (b)
 37     {
 38         if (b&1)
 39             y=y*a%mod;
 40         a=a*a%mod;
 41         b>>=1;
 42     }
 43     return y;
 44 }
 45 
 46 ll cal(ll x)
 47 {
 48     ll i,u,tot,sum=0;
 49     u=1;
 50     for (i=x;i>=x-n;i--)
 51         u=u*i%mod;
 52     for (i=0;i<=n;i++)
 53     {
 54         ///1ll
 55         tot=1ll*inv_jie[i]*inv_jie[n-i]%mod *u%mod *inv_num[x-i]%mod;
 56 //        tot=inv_jie[i]*inv_jie[n-i]%mod *u%mod *mul(x-i,mod-2)%mod;
 57         if ((n-i)&1)
 58             tot=-tot;
 59         (sum+=tot*y[i])%=mod;
 60     }
 61     return (sum+mod)%mod;
 62 }
 63 
 64 int main()
 65 {
 66     ll t,m,i,p,q,vp,vq;
 67     jie[0]=1;
 68     maxv=mod-1;
 69     for (i=1;i<=maxv;i++)
 70         ///1ll
 71         jie[i]=1ll*jie[i-1]*i%mod;
 72     inv_jie[maxv]=mul(jie[maxv],mod-2);
 73     for (i=maxv-1;i>=0;i--)
 74     {
 75         inv_jie[i]=1ll*inv_jie[i+1]*(i+1)%mod;
 76         ///1~9999991 inv
 77         inv_num[i+1]=1ll*inv_jie[i+1]*jie[i]%mod;
 78     }
 79 
 80     /**
 81     inv
 82     t*(n+2*m)
 83     6000000
 84     log(9999990) 25
 85     **/
 86 
 87 
 88     scanf("%lld",&t);
 89     while (t--)
 90     {
 91         scanf("%lld%lld",&n,&m);
 92         for (i=0;i<=n;i++)
 93             scanf("%lld",&y[i]);
 94         y[n+1]=cal(n+1);
 95         n++;
 96 
 97         ///sum 1~n
 98         for (i=1;i<=n;i++)
 99             (y[i]+=y[i-1])%=mod;
100 
101         while (m--)
102         {
103             scanf("%lld%lld",&p,&q);
104             p--;
105             vq=q<=n?y[q]:cal(q);
106             vp=p<=n?y[p]:cal(p);
107             printf("%lld
",(vq-vp+mod)%mod);///L>=1
108         }
109     }
110 
111     return 0;
112 }
113 /*
114 1
115 3 10
116 0 1 4 9
117 3 5
118 1 5
119 
120 
121 1
122 3 10
123 5 5 5 5
124 1 5
125 */

用long long，内存勉强不超。但估计在现场赛的时候，会超。

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=9999991;
 14 const int maxn=1e3+10;
 15 const int maxlen=mod+10;
 16 
 17 /**
 18 1.1~9999991 inv
 19 2.use int
 20 **/
 21 
 22 /**
 23 better way:
 24 多项式快速插值
 25 luogo5158
 26 **/
 27 
 28 ll y[maxn],jie[maxlen],inv_jie[maxlen],inv_num[maxlen],n;
 29 //ll maxv=1e3;
 30 ll maxv=mod-1;
 31 
 32 ll mul(ll a,ll b)
 33 {
 34     ll y=1;
 35     while (b)
 36     {
 37         if (b&1)
 38             y=y*a%mod;
 39         a=a*a%mod;
 40         b>>=1;
 41     }
 42     return y;
 43 }
 44 
 45 ll cal(ll x)
 46 {
 47     ll i,u,tot,sum=0;
 48     u=1;
 49     for (i=x;i>=x-n;i--)
 50         u=u*i%mod;
 51     for (i=0;i<=n;i++)
 52     {
 53         tot=inv_jie[i]*inv_jie[n-i]%mod *u%mod *inv_num[x-i]%mod;
 54 //        tot=inv_jie[i]*inv_jie[n-i]%mod *u%mod *mul(x-i,mod-2)%mod;
 55         if ((n-i)&1)
 56             tot=-tot;
 57         (sum+=tot*y[i])%=mod;
 58     }
 59     return (sum+mod)%mod;
 60 }
 61 
 62 int main()
 63 {
 64     ll t,m,i,p,q,vp,vq;
 65     jie[0]=1;
 66     maxv=mod-1;
 67     for (i=1;i<=maxv;i++)
 68         jie[i]=jie[i-1]*i%mod;
 69     inv_jie[maxv]=mul(jie[maxv],mod-2);
 70     for (i=maxv-1;i>=0;i--)
 71     {
 72         inv_jie[i]=inv_jie[i+1]*(i+1)%mod;
 73         ///1~9999991 inv
 74         inv_num[i+1]=inv_jie[i+1]*jie[i]%mod;
 75     }
 76 
 77     /**
 78     inv
 79     t*(n+2*m)
 80     6000000
 81     log(9999990) 25
 82     **/
 83 
 84 
 85     scanf("%lld",&t);
 86     while (t--)
 87     {
 88         scanf("%lld%lld",&n,&m);
 89         for (i=0;i<=n;i++)
 90             scanf("%lld",&y[i]);
 91         y[n+1]=cal(n+1);
 92         n++;
 93 
 94         ///sum 1~n
 95         for (i=1;i<=n;i++)
 96             (y[i]+=y[i-1])%=mod;
 97 
 98         while (m--)
 99         {
100             scanf("%lld%lld",&p,&q);
101             p--;
102             vq=q<=n?y[q]:cal(q);
103             vp=p<=n?y[p]:cal(p);
104             printf("%lld
",(vq-vp+mod)%mod);///L>=1
105         }
106     }
107 
108     return 0;
109 }
110 /*
111 1
112 3 10
113 0 1 4 9
114 3 5
115 1 5
116 
117 
118 1
119 3 10
120 5 5 5 5
121 1 5
122 */

求逆不进行初始化，超时

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=9999991;
 14 const int maxn=1e3+10;
 15 
 16 /**
 17 better way:
 18 多项式快速插值
 19 luogo5158
 20 **/
 21 
 22 ll y[maxn],jie[maxn],inv_jie[maxn],n;
 23 ll maxv=1e3;
 24 
 25 ll mul(ll a,ll b)
 26 {
 27     ll y=1;
 28     while (b)
 29     {
 30         if (b&1)
 31             y=y*a%mod;
 32         a=a*a%mod;
 33         b>>=1;
 34     }
 35     return y;
 36 }
 37 
 38 ll cal(ll x)
 39 {
 40     ll i,u,tot,sum=0;
 41     u=1;
 42     for (i=x;i>=x-n;i--)
 43         u=u*i%mod;
 44     for (i=0;i<=n;i++)
 45     {
 46         tot=inv_jie[i]*inv_jie[n-i]%mod *u%mod *mul(x-i,mod-2)%mod;
 47         if ((n-i)&1)
 48             tot=-tot;
 49         (sum+=tot*y[i])%=mod;
 50     }
 51     return (sum+mod)%mod;
 52 }
 53 
 54 int main()
 55 {
 56     ll t,m,i,p,q,vp,vq;
 57     ///can also calculate 1~9999991 inv
 58     jie[0]=1;
 59     for (i=1;i<=maxv;i++)
 60         jie[i]=jie[i-1]*i%mod;
 61     inv_jie[maxv]=mul(jie[maxv],mod-2);
 62     for (i=maxv-1;i>=0;i--)
 63         inv_jie[i]=inv_jie[i+1]*(i+1)%mod;
 64 
 65     scanf("%lld",&t);
 66     while (t--)
 67     {
 68         scanf("%lld%lld",&n,&m);
 69         for (i=0;i<=n;i++)
 70             scanf("%lld",&y[i]);
 71         y[n+1]=cal(n+1);
 72         n++;
 73 
 74         ///sum 1~n
 75         for (i=1;i<=n;i++)
 76             (y[i]+=y[i-1])%=mod;
 77 
 78         while (m--)
 79         {
 80             scanf("%lld%lld",&p,&q);
 81             p--;
 82             vq=q<=n?y[q]:cal(q);
 83             vp=p<=n?y[p]:cal(p);
 84             printf("%lld
",(vq-vp+mod)%mod);///L>=1
 85         }
 86     }
 87 
 88     return 0;
 89 }
 90 /*
 91 1
 92 3 10
 93 0 1 4 9
 94 3 5
 95 1 5
 96 
 97 
 98 1
 99 3 10
100 5 5 5 5
101 1 5
102 */

way2.

牛顿插值多项式

均差（差分形式）

204ms

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=9999991;
 14 const int maxn=1e3+10;
 15 
 16 ll x[maxn][maxn],n;
 17 ll jie[maxn],jie_inv[maxn];
 18 ll maxv=1e3+5;
 19 
 20 ll cal(ll v)
 21 {
 22     ll sum=0,c=1,i;
 23     for (i=0;i<=n;i++)
 24     {
 25         (sum+=x[0][i]*c)%=mod;
 26         c=c*(v-i)%mod;
 27     }
 28     return sum;
 29 }
 30 
 31 
 32 ll mul(ll a,ll b)
 33 {
 34     ll y=1;
 35     while (b)
 36     {
 37         if (b&1)
 38             y=y*a%mod;
 39         a=a*a%mod;
 40         b>>=1;
 41     }
 42     return y;
 43 }
 44 
 45 int main()
 46 {
 47     ll t,m,i,j,k,u,v,v1,v2;
 48     scanf("%lld",&t);
 49     jie[0]=1;
 50     for (i=1;i<=maxv;i++)
 51         jie[i]=jie[i-1]*i%mod;
 52     jie_inv[maxv]=mul(jie[maxv],mod-2);
 53     for (i=maxv-1;i>=0;i--)
 54         jie_inv[i]=jie_inv[i+1]*(i+1)%mod;
 55     while (t--)
 56     {
 57         scanf("%lld%lld",&n,&m);
 58         for (i=0;i<=n;i++)
 59             scanf("%lld",&x[i][i]);
 60         for (i=1;i<=n;i++)
 61             for (k=i,j=0;k<=n;k++,j++)
 62                 x[j][k]=(x[j+1][k]-x[j][k-1])%mod;
 63         v=0;
 64         for (k=n;k>=0;k--)
 65             (v+=x[k][n])%=mod;
 66         n++;
 67         x[n][n]=v;
 68 
 69 
 70         for (i=1;i<=n;i++)
 71             x[i][i]+=x[i-1][i-1];
 72 
 73         for (i=1;i<=n;i++)
 74             for (k=i,j=0;k<=n;k++,j++)
 75                 x[j][k]=(x[j+1][k]-x[j][k-1])%mod;
 76         for (i=2;i<=n;i++)
 77             for (k=i,j=0;k<=n;k++,j++)
 78                 x[j][k]=x[j][k]*jie_inv[i]%mod;
 79 
 80         while (m--)
 81         {
 82             scanf("%lld%lld",&u,&v);
 83             u--;
 84             v1=v<=n?x[v][v]:cal(v);
 85             v2=u<=n?x[u][u]:cal(u);
 86             printf("%lld
",((v1-v2)%mod+mod)%mod);
 87         }
 88     }
 89     return 0;
 90 }
 91 /*
 92 1
 93 3 10
 94 0 1 4 9
 95 3 5
 96 1 5
 97 
 98 
 99 1
100 3 10
101 5 5 5 5
102 1 5
103 */

way3.

若干个n次函数的和(i=1,2,...)

n+1次函数

直接求出n+1次函数的系数，自然数求幂

没试过，时间复杂度可能稍大，可能需要各种预处理。

见

预处理

伯努利数 https://blog.csdn.net/cj1064789374/article/details/85388995

斯特林数 https://blog.csdn.net/lyd_7_29/article/details/75041818

G. Winner

那时想的是强连通

若缩点后，形成链结构，则起点（一个强连通集合）中的所有的点为可以赢的点。

这个方法是 from https://acm.ecnu.edu.cn/wiki/index.php?title=2019_ICPC_China_Nanchang_Invitational_Programming_Contest

队友那时也是这个方法，666！

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=1e9+7;
 14 const int maxn=1e5+10;
 15 
 16 /*
 17 winners:
 18 the one(x) that can win the winner(except x)
 19 */
 20 
 21 struct node
 22 {
 23     int a[3],num;
 24 }f[3][maxn];
 25 
 26 bool use[maxn];
 27 
 28 int cmp0(node x,node y)
 29 {
 30     return x.a[0]<y.a[0];
 31 }
 32 
 33 int cmp1(node x,node y)
 34 {
 35     return x.a[1]<y.a[1];
 36 }
 37 
 38 int cmp2(node x,node y)
 39 {
 40     return x.a[2]<y.a[2];
 41 }
 42 
 43 int main()
 44 {
 45     int n,q,x[3],d[3],i,j;
 46     bool vis;
 47     scanf("%d%d",&n,&q);
 48 
 49     for (j=0;j<3;j++)
 50         for (i=1;i<=n;i++)
 51             scanf("%d",&f[0][i].a[j]);
 52     for (i=1;i<=n;i++)
 53     {
 54         f[0][i].num=i;
 55         f[1][i]=f[2][i]=f[0][i];
 56     }
 57 
 58     sort(f[0]+1,f[0]+n+1,cmp0);
 59     sort(f[1]+1,f[1]+n+1,cmp1);
 60     sort(f[2]+1,f[2]+n+1,cmp2);
 61 
 62     d[0]=d[1]=d[2]=n;
 63     x[0]=x[1]=x[2]=inf;
 64     ///f[0][0].a[0],f[1][0].a[1],f[2][0].a[2] init 0; Value > 0
 65     for (i=0;i<3;i++)
 66         if (f[i][n].a[i]>f[i][n-1].a[i])
 67         {
 68             use[f[i][n].num]=1;
 69             for (j=0;j<3;j++)
 70                 x[j]=min(x[j],f[i][n].a[j]);
 71         }
 72     while (1)
 73     {
 74         for (i=0;i<3;i++)
 75         {
 76             while (f[i][d[i]].a[i]>x[i])
 77             {
 78                 for (j=0;j<3;j++)
 79                     x[j]=min(x[j],f[i][d[i]].a[j]);
 80                 use[f[i][d[i]].num]=1;
 81                 d[i]--;
 82             }
 83         }
 84         vis=1;
 85         for (i=0;i<3;i++)
 86             if (f[i][d[i]].a[i]>x[i])
 87                 vis=0;
 88         if (vis)
 89             break;
 90     }
 91 
 92     while (q--)
 93     {
 94         scanf("%d",&i);
 95         printf("%s
",use[i]?"YES":"NO");
 96     }
 97     return 0;
 98 }
 99 /*
100 n=1
101 
102 */

H. Another Sequence

遗憾场上没做出来。。。

xor的题目

要想到fwt啊！！！

何况还是两个数组直接的操作

之后就是动态开点线段树了，

对于求根号，不会经历多少次，

初始题目，没有说求根号向下取整，差评……

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=1e9+7;
 14 const int maxg=(1e5+10)*4;
 15 const int maxn=1e7;
 16 
 17 int n,id;
 18 ll a[maxg],b[maxg],cnt[maxg];
 19 int maxs;
 20 
 21 struct node
 22 {
 23     int l,r,g,tag;
 24 }f[maxn];
 25 
 26 ///log(1e10)*1e5
 27 
 28 void fwt(ll *a)
 29 {
 30     int cnt_pre,cnt_cur,i,j;
 31     for (cnt_pre=1,cnt_cur=2;cnt_pre<maxs;cnt_pre<<=1,cnt_cur<<=1)
 32         for (i=0;i<maxs;i+=cnt_cur)
 33             for (j=0;j<cnt_pre;j++)
 34                 a[i+j+cnt_pre]+=a[i+j];
 35 }
 36 
 37 void ufwt(ll *a)
 38 {
 39     int cnt_pre,cnt_cur,i,j;
 40     for (cnt_pre=1,cnt_cur=2;cnt_pre<maxs;cnt_pre<<=1,cnt_cur<<=1)
 41         for (i=0;i<maxs;i+=cnt_cur)
 42             for (j=0;j<cnt_pre;j++)
 43                 a[i+j+cnt_pre]-=a[i+j];
 44 }
 45 
 46 void push_down(int ind)
 47 {
 48     f[f[ind].l].g+=f[ind].tag;
 49     f[f[ind].r].g+=f[ind].tag;
 50     f[f[ind].l].tag+=f[ind].tag;
 51     f[f[ind].r].tag+=f[ind].tag;
 52     f[ind].tag=0;
 53 }
 54 
 55 void update(int ind,ll l,ll r,int x,int y)
 56 {
 57     if (x<=l && r<=y)
 58     {
 59         f[ind].g++;
 60         f[ind].tag++;   ///用于传给子节点的
 61         return;
 62     }
 63     if (!f[ind].l)
 64         f[ind].l=++id;
 65     if (!f[ind].r)
 66         f[ind].r=++id;
 67     if (f[ind].tag)
 68         push_down(ind);
 69     int m=(l+r)>>1;
 70     if (x<=m)
 71         update(f[ind].l,l,m,x,y);
 72     if (m<y)
 73         update(f[ind].r,m+1,r,x,y);
 74 }
 75 
 76 int query(int ind,ll l,ll r,int x)
 77 {
 78     if (l==r)
 79         return f[ind].g;
 80     if (!f[ind].l)
 81         f[ind].l=++id;
 82     if (!f[ind].r)
 83         f[ind].r=++id;
 84     if (f[ind].tag)
 85         push_down(ind);
 86     int m=(l+r)>>1;
 87     if (x<=m)
 88         return query(f[ind].l,l,m,x);
 89     return query(f[ind].r,m+1,r,x);
 90 }
 91 
 92 int main()
 93 {
 94     int q,i,j,ci;
 95     ll x,y,num,nn;
 96     int maxv=2e5;
 97     scanf("%d",&n);
 98     for (i=0;i<n;i++)
 99     {
100         scanf("%d",&j);
101         a[j]++;
102     }
103     for (i=0;i<n;i++)
104     {
105         scanf("%d",&j);
106         b[j]++;
107     }
108 
109     maxs=1;
110     ///1e5*2 maxvalue
111     while (maxs<1e5*2)
112         maxs<<=1;
113 
114     ///(5*10^4)^2
115     fwt(a);
116     fwt(b);
117     for (i=0;i<maxs;i++)
118         a[i]=a[i]*b[i];
119     ufwt(a);
120     cnt[0]=a[0];
121     for (i=1;i<=maxv;i++)
122         cnt[i]=cnt[i-1]+a[i];
123 
124     id=1;///对应query(1,...)
125     nn=n*n;
126     scanf("%d",&q);
127     while (q--)
128     {
129         scanf("%lld%lld",&x,&y);
130         if (x==0)
131         {
132             ci=query(1,1,nn,y);
133             num=lower_bound(cnt,cnt+maxv,y)-cnt;
134             while (ci-- && num!=1)
135                 num=sqrt(num);
136             printf("%lld
",num);
137         }
138         else
139             update(1,1,nn,x,y);
140     }
141     return 0;
142 }
143 /*
144 3 3 5 5 7 7 7 7 7 7 7 7 7 7 7 10 11 13 13 14 14 14 15 15 15
145 */

验证程序

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=1e5+10;
15 
16 int a[maxn],b[maxn],c[maxn];
17 
18 int main()
19 {
20     int n,i,j;
21     scanf("%d",&n);
22     for (i=0;i<n;i++)
23         scanf("%d",&a[i]);
24     for (i=0;i<n;i++)
25         scanf("%d",&b[i]);
26     for (i=0;i<n;i++)
27         for (j=0;j<n;j++)
28             c[a[i]|b[j]]++;
29     for (i=0;i<=30;i++)
30     {
31         while (c[i]--)
32             printf("%d ",i);
33     }
34     return 0;
35 }
36 /*
37 5
38 6 2 6 4 5
39 1 7 9 10 3
40 3 3 5 5 7 7 7 7 7 7 7 7 7 7 7 10 11 13 13 14 14 14 15 15 15
41 */