[AtCoder Grand Contest 036]F - Square Constraints

제목의 뜻
좋은 문제.용척 원리를 명확히 써야 한다.i가 선택할 수 있는 pi 범위를 li~ri로 설정합니다.각 k(0<=k<=n, n~2n-1의 l은 0)에 대해 모든 pi<=ri를 만족시키려면 적어도 k개의 pi

가 있어야 하며 성질이 없으면 이 문제는 할 수 없기 때문에 처음에는 성질을 찾는 것이 틀림없다.이 문제의 가장 관건적인 성질은 0~n-1의 r인정이 l보다 크다는 것이다.0~n-1의 리-1과 n~2n-1의 r를 한 수조에 넣고 정렬하면 0~n-1은 l-1을 선택하거나 r를 선택하고, 이 구간(0~p)이 전체 순서(오른쪽 단점에 따라 정렬)에 있다는 것을 알면 공헌을 계산할 수 있다.처음에 k를 매거하여 0~n-1에서 k개가 l-1을 선택한 것을 알았고 dp[i][j]는 우리가 이 수조 안의 앞의 i개의 위치를 결정했고 j개의 위치가 l-1의 방안수를 선택하면 현재 결정된 위치가 처한 순서를 알 수 있다.이 문제는 없겠지.

#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
struct node
{
	int p,id;
}a[510];
bool cmp(node a,node b)
{
	if(a.p==b.p)return a.id>b.id;
	else return a.p<b.p;
}
int l[510],r[510],f[510][300];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n=read(),m=read();
    for(int i=0;i<2*n;i++)
    {
    	a[i].id=i;r[i]=min(2*n-1,(int)floor(sqrt(4*n*n-i*i)));
    	if(i>=n)l[i]=0,a[i].p=r[i];
    	else {l[i]=ceil(sqrt(n*n-i*i));a[i].p=l[i]-1;}
	}sort(a,a+2*n,cmp);
	int ans=0;
	for(int k=0;k<=n;k++)
	{
		int cnt=0;
		memset(f,0,sizeof(f));f[0][0]=1;
		for(int i=1;i<=2*n;i++)
		{
			if(a[i-1].id<n)cnt++;
			for(int j=0;j<=min(k,cnt);j++)
			{
				if(a[i-1].id<n)
				{
					f[i][j]=1LL*f[i-1][j]*(r[a[i-1].id]+1-(2*n-1-a[i-1].id+k-j))%m;
					if(j>0)(f[i][j]+=1LL*f[i-1][j-1]*(a[i-1].p+1-(i-1-(cnt-j)))%m)%=m;
				}
				else f[i][j]=1LL*f[i-1][j]*(a[i-1].p+1-(i-1-(cnt-j)))%m;
			}
		}
		if(k&1)(ans-=f[2*n][k]-m)%=m;
		else (ans+=f[2*n][k])%=m;
	}pr2(ans);
   	return 0;
}

[AtCoder Grand Contest 036]F - Square Constraints

좋은 웹페이지 즐겨찾기