这套题有毒，T1标程挂了，T2题面完全莫名其妙，T3没有告诉取模害我打了好久高精。。。
A题.
统计每个数后面比它小的数的个数记作f把，操作一个数就是把它后面所有比它小的数和它的f清0，然后若是它到它后面最后一个比它小的数之间有等于它的数，就把这个数的f-1
记录一下已经清0的不用再清。应该是可以直接线段树做的，但是我比较蠢就线段树套了个set，结果被wys大佬造的数据卡T了，似乎把set改成treap合并权值相同的点可以过这个数据？
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=1e5+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int n,m,sz,a[N],b[N],f[N],no[N];
20
21 template<typename T>void read(T &x) {
22 char ch=getchar(); x=0; T f=1;
23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24 if(ch=='-') f=-1,ch=getchar();
25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27
28 #define lc x<<1
29 #define rc ((x<<1)|1)
30 #define mid ((l+r)>>1)
31 int sg[N<<2];
32 void update(int x,int l,int r,int pos,int v) {
33 if(l==r) { sg[x]=v; return; }
34 if(pos<=mid) update(lc,l,mid,pos,v);
35 else update(rc,mid+1,r,pos,v);
36 sg[x]=min(sg[lc],sg[rc]);
37 }
38
39 int qry(int x,int l,int r,int ql,int qr,int v) {
40 if(sg[x]>=v) return n+1;
41 if(l>=ql&&r<=qr) {
42 if(l==r) return l;
43 if(sg[rc]<v) return qry(rc,mid+1,r,ql,qr,v);
44 else return qry(lc,l,mid,ql,qr,v);
45 }
46 int rs=n+1;
47 if(qr>mid) rs=qry(rc,mid+1,r,ql,qr,v);
48 if(rs==n+1&&ql<=mid) rs=qry(lc,l,mid,ql,qr,v);
49 return rs;
50 }
51
52 struct node {
53 int pos,a;
54 node(int pos,int a):pos(pos),a(a){}
55 friend bool operator <(const node&A,const node&B) {
56 return A.a<B.a||(A.a==B.a&&A.pos<B.pos);
57 }
58 };
59
60 set<node>s[N<<2],tps;
61 void build(int x,int l,int r) {
62 For(i,l,r)
63 s[x].insert(node(i,a[i]));
64 if(l==r) return ;
65 build(lc,l,mid); build(rc,mid+1,r);
66 }
67
68 LL qry(int x,int l,int r,int ql,int qr,int v,int rr) {
69 LL rs=0;
70 if(l>=ql&&r<=qr) {
71 while(s[x].size()>0) {
72 node tp=*s[x].begin();
73 if(tp.a>v) break;
74 if(tp.a==v&&tp.pos!=ql) {
75 if(tp.pos<rr) {
76 if(f[tp.pos]) {
77 f[tp.pos]--;
78 rs++;
79 if(f[tp.pos]) tps.insert(tp);
80 }
81 }
82 else break;
83 }
84 else {
85 rs+=f[tp.pos];
86 f[tp.pos]=0;
87 no[tp.pos]=1;
88
89 }
90 s[x].erase(tp);
91 }
92 while(tps.size()>0) {
93 node tp=*tps.begin();
94 tps.erase(tp);
95 s[x].insert(tp);
96 }
97 return rs;
98 }
99 if(qr<=mid) return qry(lc,l,mid,ql,qr,v,rr);
100 if(ql>mid) return qry(rc,mid+1,r,ql,qr,v,rr);
101 return qry(lc,l,mid,ql,qr,v,rr)+qry(rc,mid+1,r,ql,qr,v,rr);
102 }
103
104 int sum[N];
105 void add(int x,int v) {
106 for(int i=x;i<=sz;i+=(i&(-i)))
107 sum[i]+=v;
108 }
109
110 int qry(int x) {
111 int rs=0;
112 for(int i=x;i;i-=(i&(-i)))
113 rs+=sum[i];
114 return rs;
115 }
116
117 #define ANS
118 int main() {
119 #ifdef ANS
120 freopen("A.in","r",stdin);
121 freopen("A.out","w",stdout);
122 #endif
123 read(n); read(m);
124 For(i,1,n) read(a[i]),b[i]=a[i];
125 sort(b+1,b+n+1);
126 sz=unique(b+1,b+n+1)-(b+1);
127 For(i,1,n) {
128 a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
129 update(1,1,n,i,a[i]);
130 }
131 LL ans=0;
132 Rep(i,n,1) {
133 f[i]=qry(a[i]-1);
134 ans+=f[i];
135 add(a[i],1);
136 }
137 printf("%lld
",ans);
138 build(1,1,n);
139 For(i,1,m) {
140 int pos,rr;
141 read(pos);
142 rr=qry(1,1,n,pos,n,a[pos]);
143 if(rr==n+1) rr=pos;
144 if(!no[pos]) {
145 LL tt=qry(1,1,n,pos,n,a[pos],rr);
146 ans-=tt;
147 }
148 printf("%lld
",ans);
149 }
150 Formylove;
151 }
B题
题目应该是9个棋子放9个格子。
floyd跑第i个点经过k条边到第j个点的方案数，矩阵优化。统计答案的时候9!枚举每个棋子到哪个格子即可。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int p=1e9+7;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int tx[10]={0,0,1,-1},ty[10]={-1,1,0,0};
20 LL n,ans;
21
22 template<typename T>void read(T &x) {
23 char ch=getchar(); x=0; T f=1;
24 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25 if(ch=='-') f=-1,ch=getchar();
26 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28
29 struct jz {
30 LL a[9][9];
31 friend jz operator *(const jz&A,const jz&B) {
32 jz rs;
33 For(i,0,8) For(j,0,8) {
34 rs.a[i][j]=0;
35 For(k,0,8)
36 (rs.a[i][j]+=A.a[i][k]*B.a[k][j]%p)%=p;
37 }
38 return rs;
39 }
40 }bs,rs;
41
42 void ksm(LL b) {
43 while(b) {
44 if(b&1) rs=rs*bs;
45 bs=bs*bs;
46 b>>=1;
47 }
48 }
49
50 int vis[10];
51 void dfs(int pos,LL now) {
52 if(!now) return;
53 if(pos==9) {
54 ans=(ans+now)%p;
55 return ;
56 }
57 For(i,0,8) if(!vis[i]) {
58 vis[i]=1;
59 dfs(pos+1,now*rs.a[pos][i]%p);
60 vis[i]=0;
61 }
62 }
63
64 int get(int x,int y) { return (x-1)*3+y-1;}
65
66 #define ANS
67 int main() {
68 #ifdef ANS
69 freopen("B.in","r",stdin);
70 freopen("B.out","w",stdout);
71 #endif
72 For(i,0,8) For(j,0,8) {
73 rs.a[i][j]=bs.a[i][j]=0;
74 if(i==j) rs.a[i][j]=1;
75 }
76 For(i,0,8) bs.a[i][i]=1;
77 For(x,1,3) For(y,1,3) {
78 For(t,0,3) if(x+tx[t]>=1&&x+tx[t]<=3&&y+ty[t]>=1&&y+ty[t]<=3) {
79 bs.a[get(x,y)][get(x+tx[t],y+ty[t])]=1;
80 }
81 }
82 read(n);
83 ksm(n);
84 dfs(0,1);
85 printf("%lld
",ans);
86 Formylove;
87 }
C题
60分可以莫比乌斯反演，场上以为要写高精于是这是一个莫比乌斯加高精的30分代码。。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=1e6+7;
16 typedef long long LL;
17 typedef double db;
18 const LL base=1e9;
19 using namespace std;
20 LL n,k;
21
22 template<typename T>void read(T &x) {
23 char ch=getchar(); x=0; T f=1;
24 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
25 if(ch=='-') f=-1,ch=getchar();
26 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
27 }
28
29 struct GJ {
30 LL a[100];
31 int len;
32 friend GJ operator +(const GJ&A,const GJ&B) {
33 GJ C;
34 C.len=max(A.len,B.len);
35 LL tp=0;
36 For(i,0,C.len) {
37 C.a[i]=(i>A.len?0:A.a[i])+(i>B.len?0:B.a[i])+tp;
38 tp=C.a[i]/base;
39 if(C.a[i]>=base) C.a[i]=C.a[i]%base;
40 }
41 while(tp!=0) {
42 C.a[++C.len]=(tp>=base?tp%base:tp);
43 tp/=base;
44 }
45 return C;
46 }
47 friend GJ operator -(const GJ&A,const GJ&B) {
48 GJ C;
49 C.len=A.len;
50 LL tp=0;
51 For(i,0,C.len) {
52 C.a[i]=A.a[i]-(i>B.len?0:B.a[i])-tp;
53 if(C.a[i]<0) {
54 C.a[i]+=base;
55 tp=1;
56 }
57 else tp=0;
58 }
59 while(C.len&&C.a[C.len]==0) {
60 C.len--;
61 }
62 return C;
63 }
64 friend GJ operator *(const GJ&A,const GJ&B) {
65 GJ C;
66 C.len=A.len+B.len+1;
67 For(i,0,C.len) C.a[i]=0;
68 For(i,0,A.len) For(j,0,B.len) {
69 C.a[i+j]+=A.a[i]*B.a[j];
70 if(C.a[i+j]>=base) {
71 C.a[i+j+1]+=C.a[i+j]/base;
72 C.a[i+j]%=base;
73 }
74 }
75 while(C.len&&C.a[C.len]==0) {
76 C.len--;
77 }
78 return C;
79 }
80 };
81
82 void print(GJ x) {
83 Rep(i,x.len,0) {
84 if(i!=x.len) printf("%.9lld",x.a[i]);
85 else printf("%lld",x.a[i]);
86 }
87 }
88
89 void put_it(GJ &A,LL x) {
90 if(x==0) {
91 A.len=0,A.a[0]=0;
92 }
93 else {
94 A.len=-1;
95 LL tp=x;
96 while(tp) {
97 A.a[++A.len]=tp%base;
98 tp/=base;
99 }
100 }
101 }
102
103 GJ ksm(LL a,LL b) {
104 GJ rs,bs;
105 rs.len=0;
106 rs.a[0]=1;
107 put_it(bs,a);
108 while(b) {
109 if(b&1) rs=rs*bs;
110 bs=bs*bs;
111 b>>=1;
112 }
113 return rs;
114 }
115
116 LL gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }
117
118 int mu[N],bo[N],p[N];
119 void get_prime() {
120 mu[1]=1;
121 For(i,2,n) {
122 if(!bo[i]) {
123 p[++p[0]]=i; mu[i]=-1;
124 }
125 for(int j=1;j<=p[0]&&p[j]*i<=n;j++) {
126 bo[p[j]*i]=1;
127 if(i%p[j]==0) {
128 mu[p[j]*i]=0;
129 break;
130 }
131 mu[p[j]*i]=-mu[i];
132 }
133 }
134 }
135
136 #define ANS
137 int main() {
138 #ifdef ANS
139 freopen("C.in","r",stdin);
140 freopen("C.out","w",stdout);
141 #endif
142 read(n); read(k);
143 GJ ans;
144 ans.len=0;
145 ans.a[0]=0;
146 get_prime();
147 For(d,1,n) {
148 GJ D=ksm(d,k),tp;
149 tp.len=0; tp.a[0]=0;
150 For(i,1,n/d) if(mu[i]==1){
151 int x=i*d;
152 GJ tt;
153 put_it(tt,(LL)(n/x)*(n/x));
154 tp=tp+tt;
155 }
156 For(i,1,n/d) if(mu[i]==-1) {
157 int x=i*d;
158 GJ tt;
159 put_it(tt,(LL)(n/x)*(n/x));
160 tp=tp-tt;
161 }
162 ans=ans+D*tp;
163 }
164 print(ans);
165 Formylove;
166 }
167 /*
168 1000 5
169
170 1000000 5
171 */
正解是随便化一下化成杜教筛的样子，然后杜教筛。先坑着，哪天没事做可能会打吧，，