题意

分析

考场50分

旁边的L君告诉我，求的就是非升子序列的个数，于是写了个树状数组。

但是\(\mod{2333} > 0\)还需要组合数中没有2333的倍数，所以实际上只得了\(a_i \leq 2333\)的部分分，还好。

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define il inline

#define co const

#pragma GCC optimize ("O0")

using namespace std;

template<class T> il T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=3e5+7,mod=1e9+7;

int n;

int a[MAXN],b[MAXN];

int rnk(int x)

{

	return lower_bound(b+1,b+n+1,x)-b;

}

int f[MAXN];

int lowbit(int x)

{

	return x&-x;

}

void add(int p,int v)

{

	for(int i=p;i<=n+1;i+=lowbit(i))

	{

		(f[i] += v) %= mod;

	}

}

int sum(int p)

{

	int res=0;

	for(int i=p;i;i-=lowbit(i))

	{

		(res += f[i]) %= mod;

	}

	return res;

}

int main()

{

  freopen("hangzhou.in","r",stdin);

  freopen("hangzhou.out","w",stdout);

	read(n);

	for(int i=1;i<=n;++i)

		b[i]=read(a[i]);

	sort(b+1,b+n+1);

	add(n+1,1);

	for(int i=1;i<=n;++i)

	{

		int p=rnk(a[i]);

		add(p,(sum(n+1) + mod - sum(p-1)) % mod);

	}

	printf("%d\n",(sum(n) + mod - n) % mod);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

标解

其实是lucas定理的运用。这跟CTSC2017吉夫特有相似之处。

由于\(a_i<233333\)，所以表示成2333进制最多有2位，所以有

转化成二维点的右上角矩阵内的方案数查询，用二维树状数组维护。

时间复杂度\(O(n \log^2 p)\)

代码实现的时候为了适应树状数组查询左下角，将下标取成相反数+p。

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define il inline

#define co const

#pragma GCC optimize ("O0")

using namespace std;

template<class T> il T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int mod=1e9+7,p=2333;

int c[p+7][p+7];

int lowbit(int x)

{

	return x&-x;

}

void add(int x,int y,int v)

{

	for(int i=x;i<=p;i+=lowbit(i))

		for(int j=y;j<=p;j+=lowbit(j))

			(c[i][j] += v) %= mod;

}

int sum(int x,int y)

{

	int res=0;

	for(int i=x;i;i-=lowbit(i))

		for(int j=y;j;j-=lowbit(j))

			(res += c[i][j]) %= mod;

	return res;

}

int main()

{

  freopen("hangzhou.in","r",stdin);

  freopen("hangzhou.out","w",stdout);

	int n;

	read(n);

	int ans=0;

	while(n--)

	{

		int x,y;

		read(x);

		y = p - x % p;

		x = p - x / p;

		int t = sum(x,y);

		(ans += t) %= mod;

		add(x,y,t + 1);

	}

	printf("%d\n",ans);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}