T1
先筛出\([2,min(\sqrt r,k)]\)里的质数，再用它们在\([max(l,2*p),r]\)里打标记，没标记的是类素数
筛到\(\sqrt r\) 就可以枚举到r的所有素数，所以取\(min(\sqrt r,k)\)，复杂度就到\(O(\sqrt r \log\log n)\)
可以看出在筛出小区间的大素数上，埃氏筛比线性筛更易操作
T2
设\(dp[i]\)表示以i结尾的子序列个数，转移方程
\[dp[i]=\sum _{j=1}^{n}dp[j]+1 \]因为可以在每个序列的末尾加个i，同时i自己单独算个子序列
当下一个元素不确定时，最优选择是选dp值最小的转移，因为方程可以写成
\[dp[i]=\sum_{j=1,j!=1}^{n}dp[j]+dp[i]+1 \]相当于将其他dp加起来怼到一个dp上，为了时方案数尽量多，肯定是其他的dp加起来尽量大，那就是选当前最小dp转移
在前n个转移完了之后，要做的就是选当前dp最小的，填上所有dp的和+1，然后它就变成了最大的，这个过程可以用矩阵快速幂实现
注意求完前n个的方案数后要排序，不能直接sort，因为要取模，所以按最晚出现的位置排序
代码
T1
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+11;
bool jud[N];
bool fp[N];
int p[N];
int num;
int l,r,k;
int sqr;
void get_prime()
{
fp[1]=1;
fp[0]=1;
sqr=min(sqr,k);
for(int i=2;i<=sqr;i++)
{
if(!fp[i])
p[++num]=i;
for(int j=1;j<=num&&p[j]*i<=sqr;j++)
{
fp[p[j]*i]=1;
if(i%p[j]==0)
break;
}
}
return;
}
void get_ans()
{
for(int i=1;i<=num;i++)
{
int st=max(l/p[i],2ll);
int ed=r/p[i];
for(int j=st;j<=ed;j++)
jud[j*p[i]-l]=1;
}
return;
}
signed main()
{
cin>>l>>r>>k;
sqr=sqrt(r);
get_prime();
get_ans();
int ans=0;
for(int j=0;j<=r-l;j++)
if(!jud[j])
ans^=(l+j);
cout<<ans<<endl;
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+11;
const long long mod=1e9+7;
struct mat_{
long long mat[102][102];
int h,l;
}x,as,c;
struct dp_{
int sum,last;
friend bool operator<(dp_ a,dp_ b)
{
return a.last<b.last;
}
}f[N];
long long n,m,k;
int a[N];
int last[N];
inline long long read()
{
long long s=0;
char ch=getchar();
while(ch>'9'||ch<'0')
ch=getchar();
while(ch>='0'&&ch<='9')
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s;
}
void fma()
{
as.l=k+1;
as.h=k+1;
for(int i=1;i<=k-1;i++)
as.mat[i][i+1]=1;
for(int i=1;i<=k+1;i++)
as.mat[k][i]=1;
as.mat[k+1][k+1]=1;
long long y=m;
while(y)
{
if(y&1)
{
c.h=as.h;
c.l=x.l;
for(int i=1;i<=as.h;i++)
for(int j=1;j<=x.l;j++)
{
long long s=0;
for(int k=1;k<=as.l;k++)
s+=as.mat[i][k]*x.mat[k][j]%mod;
c.mat[i][j]=s%mod;
}
x=c;
}
c.h=as.h;
c.l=as.l;
for(int i=1;i<=as.h;i++)
for(int j=1;j<=as.l;j++)
{
long long s=0;
for(int k=1;k<=as.l;k++)
s+=as.mat[i][k]*as.mat[k][j]%mod;
c.mat[i][j]=s%mod;
}
as=c;
y>>=1;
}
return;
}
signed main()
{
long long ans=0;
n=read();
m=read();
k=read();
for(int i=1;i<=n;i++)
a[i]=read();
long long sum=0;
for(int i=1;i<=n;i++)
{
long long maxn=f[a[i]].sum;
f[a[i]].sum=(sum+1)%mod;
sum=(f[a[i]].sum+sum-maxn+mod)%mod;
f[a[i]].last=i;
}
sort(f+1,f+k+1);
x.h=k+1;
x.l=1;
for(int i=1;i<=k;i++)
x.mat[i][1]=f[i].sum;
x.mat[k+1][1]=1;
fma();
for(int i=1;i<=k;i++)
ans=(ans+x.mat[i][1])%mod;
cout<<ans%mod<<endl;
return 0;
}