这场题好弱啊qwq
先发代码再填坑
坑已填qwq
T1 bzoj4415
题目大意就是，有一个环，编号1-N，一开始指针在1，有一个长度为n的序列p，每次指针向后移pi个，然后把那个点删掉。
问所有点被删掉的顺序
然后用树状数组维护每个点有没有被删掉，然后就可以通过树状数组上二分求出每次删除的位置。然后就做完了
（以前不会树状数组上二分啊...一直写的log^2的二分...不过稍微YY一下就会了）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define N 700005 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} int n;
struct BIT{
int c[N];
int lowbit(int x){return x&-x;}
void load(){
memset(c,0,sizeof(c));
for (int i=1;i<=n;++i){
++c[i];
if (i+lowbit(i)<=n) c[i+lowbit(i)]+=c[i];
}
}
int solve(int sum){
int x=0,now=0;
for (int i=(1<<20);i;i=i>>1)
if (x+i<=n&&now+c[x+i]<sum){
x+=i;now+=c[x];
}
for (int i=(++x);i<=n;i+=lowbit(i)) --c[i];
return x;
}
} bit; int main(){
n=read();
bit.load();
int now=n,sum=n;
for (int i=n;i;--i){
int x=read()%i+1;
if (i-sum>=x) sum=sum+x-1;
else sum=x+sum-i-1;
printf("%d\n",bit.solve(sum+1));
}
return 0;
}
T2 bzoj4416
题目大意是，给你一个字符串，长度l<=450，由n<=26个字母组成，要你判断 所有n个字母的排列是否都是这个给定串的子串（可以不连续）
Claris好神啊！
首先预处理出next[i][x]表示第i位之后最近的字母x的位置（不存在就l+1），然后dp[mask]表示集合为mask最早被全员匹配的位置，然后枚举最后出现的字母进行转移。
然后就做完了，dp[全1状态]<=l就是yes
啊..对..还有一个特判，就是我们可以发现满足要求的串最短是n^2级别的，所以如果n>21直接输出NO
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 30
#define L 505 using namespace std;
int n,l;char s[L];
int nxt[L][N],dp[1<<21^233]; inline int lowbit(int x){return x&-x;} bool work(){
scanf("%d%s",&n,s+1);l=strlen(s+1);
if (n>21) return 0;
for (int i=0;i<n;++i) nxt[l+1][i]=l+1;
for (int i=l;i>=0;--i){
for (int j=0;j<n;++j) nxt[i][j]=nxt[i+1][j];
if (i) nxt[i][s[i]-'a']=i;
}
for (int i=dp[0]=0;i<(1<<n);dp[++i]=0)
for (int j=0;j<n;++j)if ((i&(1<<j))>0)
dp[i]=max(dp[i],nxt[dp[i^(1<<j)]][j]);
return dp[(1<<n)-1]<=l;
} int main(){
int testnumber;scanf("%d",&testnumber);
while (testnumber--) puts(work()?"YES":"NO");
return 0;
}
T3 bzoj4417
傻逼矩阵乘法，n*2个状态表示跳奇数&偶数次每行的方案数，然后有2个转移矩阵一个是奇to偶另一个是偶to奇，随便YY一下快速幂就行了。
然而发现我的代码长度运行时间还有内存都是其他人的3倍左右QAQ一定是我傻逼了TAT
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define P 30011 using namespace std; struct matrix{
int x,y;
int a[105][105];
matrix(){}
matrix(int _x,int _y):x(_x),y(_y){}
matrix(int _x){
x=y=_x;
memset(a,0,sizeof(a));
for (int i=1;i<=_x;++i) a[i][i]=1;
}
} A,B,C,D; inline matrix operator *(matrix a,matrix b){
if (a.y!=b.x) swap(a,b);
matrix ret=matrix(a.x,b.y);
int z=a.y;
for (int i=1;i<=ret.x;++i)
for (int j=1;j<=ret.y;++j){
ret.a[i][j]=0;
for (int k=1;k<=z;++k)
(ret.a[i][j]+=(ll)a.a[i][k]*b.a[k][j]%P)%=P;
}
return ret;
} matrix pow(matrix x,int y){
matrix ret=matrix(x.x);
while (y){
if (y&1) ret=ret*x;
y/=2;
x=x*x;
}
return ret;
} int main(){
int n,m;scanf("%d%d",&n,&m);
if ((--m)==1){printf("%d\n",n<=2);return 0;}
A=matrix(2*n);B=matrix(2*n);
for (int i=1;i<=n;++i)
for (int j=max(i-1,1);j<=i+1&&j<=n;++j)
++A.a[j][i+n],++B.a[j+n][i];
int ans=0;
if (m&1){
C=A*B;
D=B*pow(C,m/2-1);
ans=D.a[2*n][1];
D=D*C;
ans=(D.a[2*n][1]-ans+P)%P;
}
else{
C=A*B;
D=pow(C,m/2-1);
ans=D.a[n][1];
D=D*C;
ans=(D.a[n][1]-ans+P)%P;
}
printf("%d\n",ans);
return 0;
}