description

analysis

注意配出来的饮料不可以再配成其他饮料，所以肯定有\(O(n^2)\)的枚举
而且可口度两两互不相同，搞得我以为这是神仙题
考虑把两个试剂\([l_1,r_1],[l_2,r_2]\)合并，\([l_1+l_2,r_1+r_2]\)里的每个点都有贡献
假设贡献只有\(1\)，拉出来就是\(1,2,3,..,k-1,k,k,k,...,k,k-1,...,3,2,1\)
注意到前面一段和后面一段是等差数列，中间全部相等，做一遍差分
就会是\(0,1,1,...,1,1,0,0,...,0,-1,...,-1,-1,-1,-1\)，注意最后面多出来一个\(-1\)
再做差分，变成\(0,1,0,...,0,0,-1,0,...,0,-1,...,0,0,0,0,1\)，最后面又多出来一个\(1\)
那么对于一次贡献，相当于打上两个加两个减标记，最后两次前缀和还原原数组

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 5005

#define MAX 20000005

#define ha 998244353

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll v[MAXN],l[MAXN],r[MAXN];

ll a[MAX];

ll n,m,mx;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline void swap(ll &x,ll &y){ll z=x;x=y,y=z;}

int main()

{

	//freopen("T1.in","r",stdin);

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

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

	n=read(),m=read();

	fo(i,1,n)v[i]=read(),l[i]=read(),mx=max(mx,r[i]=read());

	fo(i,1,n-1)fo(j,i+1,n)

	{

		ll lx=l[i],rx=r[i],ly=l[j],ry=r[j],k,kk,tmp=v[i]*v[j]%ha;

		(a[lx+ly]+=tmp)%=ha,(a[lx+ry+1]-=tmp)%=ha,(a[rx+ly+1]-=tmp)%=ha,(a[rx+ry+2]+=tmp)%=ha;

	}

	fo(i,1,2*mx+1)(a[i]+=a[i-1])%=ha;

	fo(i,1,2*mx+1)(a[i]+=a[i-1])%=ha;

	while (m--)printf("%lld\n",(a[read()]+ha)%ha);

	return 0;

}

巴特西

【JZOJ6384】珂学家

description

analysis

code

最新文章

热门文章