（某咕咕咕的人在咕咕咕了咕咕咕天之后，又准备开始写博客了）

今天得分：30+0+0。T3算错了空间，50分没了。。。

T1

题目大意：一个圆上有3n个不同的点，每个点都被染成了n种颜色中的一种。每种颜色恰好出现了3次。对每种颜色画一条圆弧，满足其两端点的颜色都是c且不经过另一个颜色为c的点。要求这n条圆弧互不相交。求画圆弧的方案数。n<=2e5

题解：容易发现，该图最多选择的圆弧数为n，于是我们只需要求最大匹配的方案数，随便dp即可。关于环转化成链，我们只需要枚举第一个点的那种颜色选择圆弧的方法，就可以不重不漏统计方案。时间复杂度O(N)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x*f;
}
const int mo=998244353;
int n,n3,n6,ans;
int a[1200010],las[1200010],pla[200010],to[1200010];
struct node{int num;int ans;}dp[1200010];
inline int jia(int x,int y){x+=y;if(x>=mo)x-=mo;return x;}
inline void solve(int bg,int fro)
{
	register int i,j;//cout<<"   "<<bg<<" "<<fro<<endl;
	memset(dp,0,sizeof(dp));
	dp[fro-bg]=(node){1,1};
	for(i=fro-bg+1;i<=n3;++i)
	{
	dp[i]=dp[i-1];
	if(las[bg+i]>bg)
	{
	if(dp[las[bg+i]-bg-1].num+1>dp[i].num){dp[i]=dp[las[bg+i]-bg-1];++dp[i].num;}
	else if(dp[las[bg+i]-bg-1].num+1==dp[i].num)dp[i].ans=jia(dp[i].ans,dp[las[bg+i]-bg-1].ans);
	}//cout<<i<<" "<<i+bg<<" "<<dp[i].num<<" "<<dp[i].ans<<endl;
	}
	if(dp[n3].num==n)ans=jia(ans,dp[n3].ans);
}
int main()
{
	freopen("arc.in","r",stdin);
	freopen("arc.out","w",stdout);
	register int i,la=0;
	n=re_ad();n3=n*3;n6=n3*2;
	for(i=1;i<=n3;++i)a[i]=a[i+n3]=re_ad();
	for(i=1;i<=n6;++i)
	{
	las[i]=pla[a[i]];to[pla[a[i]]]=i;
	pla[a[i]]=i;
	}
	solve(0,to[1]);
	solve(to[1]-1,to[to[1]]);
	solve(to[to[1]]-1,n3+1);
	cout<<ans<<endl;return 0;
	//for(i=1;i<=n6;++i)cout<<i<<" "<<las[i]<<endl;
}

T2

题目大意：求有多少个正整数x满足c[0]*x^a[0]+c[1]*x^a[1]+...+c[n-1]*x^a[n-1]能被x^0+x^1+...+x^(m-1)整除，其中c和a是两个给定的序列。n<=1e5,m,ai<=1e9,|ci|=1 。

题解：特判x=1，之后把原式变成f(x)*(x-1) mod (x^m-1)。得到取模之后的式子后，设每一项的系数为ki，则我们只需要判断在2-max(ki+1)范围内的数即可。判断x0的时候，对于ki>=x0的部分，k[i]-=x0,k[(i+1)%m]++;对于ki<=-x0的部分，k[i]+=x0,k[(i+1)%m]--;最后判断最终的ki是否全等于0或全等于1-x0或全等于x0-1即可。由于每次操作ki的绝对值减少x0-1，总操作次数为调和级数级别，用map维护操作，并每次撤回操作，即可达到时间复杂度O(nlog^2n)。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x*f;
}
int T;
int n,m;
map<int,int> mp;
map<int,int>::iterator it;
int c[100010],a[100010],ans;
int z[2000010],num;
inline int ma(int x,int y){return x>y?x:y;}inline int ab(int x){return x>0?x:-x;}
struct node{int id,num;};
stack<node> cz;
int main()
{
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
	register int i,j;
	register int x,y,b;
	register node f;
	register int fl;bool fla;
	T=re_ad();
	while(T--)
	{
	n=re_ad();m=re_ad();mp.clear();ans=0;num=0;
	for(i=1;i<=n;++i)
	{
	c[i]=re_ad();a[i]=re_ad();num+=c[i];
	mp[(a[i]+1)%m]+=c[i];mp[(a[i])%m]-=c[i];
	}
	if(num%m==0)++ans;
	z[0]=0;fl=0;
	for(it=mp.begin();it!=mp.end();++it)
	{
	z[++z[0]]=(*it).first;fl=ma(fl,ab((*it).second));
	}
	if(!fl){puts("-1");continue;}
	for(i=fl+1;i>=2;--i)
	{
	while(z[0])
	{
	x=z[z[0]--];y=mp[x];b=y/i;
	cz.push((node){x,b});mp[(x+1)%m]+=b;mp[x]-=b*i;
	if(b!=0)z[++z[0]]=(x+1)%m;
	}
	fl=mp.begin()->second;fla=true;
	if(fl==0||fl==1-i||fl==i-1)
	for(it=mp.begin();it!=mp.end();++it)
	{
	x=(*it).second;if(x!=fl){fla=false;break;}
	}
	else fla=false;
	if(fla)++ans;
	while(!cz.empty())
	{
	f=cz.top();cz.pop();x=f.id;y=f.num;
	if(y){mp[(x+1)%m]-=y;mp[x]+=y*i;--z[0];if(!mp[x])mp.erase(x);if(!mp[(x+1)%m])mp.erase((x+1)%m);}
	z[++z[0]]=x;
	}
	}
	printf("%d\n",ans);
	}
}

T3

题目大意：

（

题解做法：

（我才不会说放图片是因为pdf复制的内容过于难受）

%%%lsz巨佬，给出了一个复杂度O(log2^2n)预处理题解中的m的做法：

把选0看做选左子树，选1看做选右子树，做和上面一样的dp，打出一个比较大的表，观察左右子树的转移点，会发现在一段内左子树大小递增而右子树大小不变，下一段右子树大小递增而左子树大小不变，我们将这些点称为转折点。

观察转折点的性质，发现每个转折点来自的左子树和右子树的大小也是一个转折点，并且左右子树的D的增量相同。于是我们小数据暴力，大数据通过转移点的合成得到转移点（其实每个转移点对应着上面做法中的一个m），注意2^n的特殊情况即可。

对于每组询问，二分查找离它最近的转移点，统计即可。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline long long re_ad()
{
	long long x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
	return x*f;
}
int T;
int lg[1000010];long long num[1000010],n;
long long dp[1000010],base[70];
queue<long long> z1,z2;
int z1cs[]={14,15,16,18,19},z2cs[]={8,9,11,12,14,15,15,16,18,19};
long long sum[3000],zd[3000],zs[3000],mx=1100000000000000ll;
int cnt,zt;
inline long long query(long long n)
{
	int pla=upper_bound(zd+1,zd+zt+1,n)-zd;
	return sum[pla-1]+1ll*(n-zd[pla-1])*zs[pla];
}
int main()
{
	freopen("dictionary.in","r",stdin);
	freopen("dictionary.out","w",stdout);
	register int i,j,las=5;
	register long long tmp;
	n=1000000;
	for(i=1;i<=1000000;++i)lg[i]=lg[i>>1]+1,num[i]=num[i-1]+lg[i];
	dp[1]=1;las=1;
	for(i=2;i<=n;++i)
	{
	j=1;dp[i]=dp[j]+dp[i-j]+num[i];
	for(j=las;j<i;++j)if(num[j]+dp[j]+dp[i-j]+num[i]<=dp[i])
	{dp[i]=min(dp[i],num[j]+dp[j]+dp[i-j]+num[i]);las=j;}else if(j-las>5)break;
	}
	for(i=0;i<5;++i)z1.push(z1cs[i]);for(i=0;i<10;++i)z2.push(z2cs[i]);
	base[0]=1;for(i=1;i<=63;++i)base[i]=base[i-1]<<1;
	tmp=22;las=5;cnt=22;
	while(1)
	{
	tmp=z1.front()+z2.front();
	if(tmp>mx)break;
	if(tmp>=base[las]-1)
	{
	zd[++zt]=base[las]-1;zs[zt]=++cnt;
	z1.push(zd[zt]);z2.push(base[las]-1);z2.push(base[las]-1);++las;
	}
	zd[++zt]=tmp;zs[zt]=++cnt;
	z1.push(tmp);z2.push(tmp);z1.pop();z2.pop();
	}//cout<<zt<<" "<<zd[zt];
	sum[1]=339;
	for(i=2;i<=zt;++i)sum[i]=sum[i-1]+1ll*(zd[i]-zd[i-1])*zs[i];
	//for(i=1;i<=zt;++i)cout<<zd[i]<<" "<<zs[i]<<endl;
	T=re_ad();
	while(T--)
	{
	n=re_ad();
	if(n<=500000)printf("%lld\n",dp[n]);
	else printf("%lld\n",query(n));
	}
	return 0;
}

?