QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620299#9380. MatchLautisticycAC ✓126ms4604kbC++143.6kb2024-10-07 17:24:412024-10-07 17:24:59

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 17:24:59]
  • 评测
  • 测评结果:AC
  • 用时:126ms
  • 内存:4604kb
  • [2024-10-07 17:24:41]
  • 提交

answer

/*
先建两棵trie.
如果k这位是1,那么合并l[one],r[ano]和r[one],l[ano]的答案。
如果k这位是0,那么交叉选的直接可行,枚举两种交叉各选了多少个。
然后下去记忆化。lone,lano和rone,rano。
dp[i][j][k1][k2][o]表示one在i,ano在j,上边交叉的时候选走了k1,k2个时,这里又选了o个的方案数。
------------------------------------------------------------------------
反正怎么选都可以,就合并的时候再选啦。
*/
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353,btm=59;
long long qpow(long long bas,long long tim)
{
	long long res=1;
	while(tim)
	{
		if(tim&1)	res=res*bas%mod;
		bas=bas*bas%mod;
		tim>>=1;
	}
	return res;
}
long long totnc,n,k,a[210],b[210],roota=1,rootb=2,cntot=2,fac[210],inv[210];
long long C(long long x,long long y)
{
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
struct node
{
	long long ch[2],siz;
}nodes[30010];
struct arrr
{
	long long num[210],len;
}ans;
arrr quer(long long one,long long ano,long long bt)
{
	arrr ret=ans;
	if(!one||!ano)
	{
		ret.num[0]=1;
		return ret;
	}
	if(bt==-1)
	{
		for(long long i=0;i<=min(nodes[one].siz,nodes[ano].siz);++i)	ret.num[i]=C(nodes[one].siz,i)*C(nodes[ano].siz,i)%mod*fac[i]%mod;
		ret.len=min(nodes[one].siz,nodes[ano].siz);
	}
	else
	{
		if((k>>bt)&1)
		{
			arrr les=quer(nodes[one].ch[0],nodes[ano].ch[1],bt-1),res=quer(nodes[one].ch[1],nodes[ano].ch[0],bt-1);
			for(long long i=0;i<=les.len;++i)
			{
				for(long long j=0;j<=res.len;++j)	ret.num[i+j]=(ret.num[i+j]+les.num[i]*res.num[j])%mod;
			}
			ret.len=les.len+res.len;
		}
		else
		{
			arrr les=quer(nodes[one].ch[0],nodes[ano].ch[0],bt-1),res=quer(nodes[one].ch[1],nodes[ano].ch[1],bt-1);
			// printf("               %lld %lld %lld %lld\n",res.len,nodes[nodes[one].ch[1]].siz,nodes[nodes[ano].ch[1]].siz,les.len);
			for(long long i=0;i<=les.len;++i)
			{
				for(long long j=0;j<=res.len;++j)
				{
					long long tmp1=les.num[i]*res.num[j]%mod;
					for(long long k=0;k<=min(nodes[nodes[one].ch[0]].siz-i,nodes[nodes[ano].ch[1]].siz-j);++k)
					{
						long long tmp2=tmp1*C(nodes[nodes[one].ch[0]].siz-i,k)%mod*C(nodes[nodes[ano].ch[1]].siz-j,k)%mod*fac[k]%mod;
						for(long long l=0;l<=min(nodes[nodes[ano].ch[0]].siz-i,nodes[nodes[one].ch[1]].siz-j);++l)
						{
							long long tmp3=C(nodes[nodes[ano].ch[0]].siz-i,l)%mod*C(nodes[nodes[one].ch[1]].siz-j,l)%mod*fac[l]%mod;
							ret.num[i+j+k+l]=(ret.num[i+j+k+l]+tmp2%mod*tmp3)%mod;
							ret.len=max(ret.len,i+j+k+l);
							// printf("%d %d %d %d\n",i,j,k,l);
						}
					}
				}
			}
		}
	}
	// printf("   %lld %lld %lld %lld:",one,ano,bt,ret.len);
	// for(long long i=0;i<=n;++i)	printf(" %lld",ret.num[i]);
	// printf("\n");
	return ret;
}
int main()
{
	// freopen("sample.in","r",stdin);
	scanf("%lld %lld",&n,&k);
	fac[0]=1;
	for(long long i=1;i<=n;++i)	fac[i]=fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2);
	for(long long i=n-1;i>=0;--i)	inv[i]=inv[i+1]*(i+1)%mod;
	for(long long i=1;i<=n;++i)	scanf("%lld",&a[i]);
	for(long long i=1;i<=n;++i)	scanf("%lld",&b[i]);
	for(long long i=1;i<=n;++i)
	{
		long long now=roota;
		for(long long j=btm;j>=0;--j)
		{
			if(!nodes[now].ch[(a[i]>>j)&1])	nodes[now].ch[(a[i]>>j)&1]=++cntot;
			now=nodes[now].ch[(a[i]>>j)&1];
			++nodes[now].siz;
		}
		now=rootb;
		for(long long j=btm;j>=0;--j)
		{
			if(!nodes[now].ch[(b[i]>>j)&1])	nodes[now].ch[(b[i]>>j)&1]=++cntot;
			now=nodes[now].ch[(b[i]>>j)&1];
			++nodes[now].siz;
		}
	}
	ans=quer(roota,rootb,btm);
	for(long long i=1;i<=n;++i)	printf("%lld\n",ans.num[i]);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4132kb

input:

9 5
1 7 2 8 4 9 2 5 10
1 3 2 4 5 8 8 8 9

output:

51
1034
10768
62195
200965
348924
294444
97344
7200

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 126ms
memory: 4604kb

input:

200 569102225177443347
1103663383682482176 1103381908705771520 1099441259031822336 1098878309078401024 1089871109823660032 1080863910568919040 1074108511127863296 1071856711314178048 1069041961547071488 1068479011593650176 1067353111686807552 1062849512059437056 1049338713177325568 10448351135499550...

output:

20506
208107723
47878304
53020813
972282728
933586852
658157196
670189811
957980024
366179738
217980591
967482558
833450149
987731802
260904367
5263881
600332344
906061351
658256294
93700706
421323952
178075016
219871690
986880524
848776106
191185484
641917326
576497440
908609746
349728876
606714342...

result:

ok 200 lines

Test #3:

score: 0
Accepted
time: 9ms
memory: 4592kb

input:

200 1098723432450995412
972777519512027136 936748722493063168 864691128455135232 860187528827764736 857935729014079488 856246879153815552 855683929200394240 851180329573023744 848928529759338496 847802629852495872 847310048643252224 847239679899074560 846676729945653248 828662331436171264 8280993814...

output:

8320
34035512
428014253
916072411
696504298
748377440
32424677
188402417
233587075
130639672
759476380
546285625
187068736
159002787
131866334
381530906
133126344
373727612
923311054
725293681
718162548
39511135
322320638
44709653
156884882
285926751
787179409
282967016
153092344
615721347
950855850...

result:

ok 200 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

200 1
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

3072
4412928
940025853
665370743
752672705
581549490
41990996
541401698
170451802
26584141
220983766
844620126
64506869
137621326
418866920
351049174
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 4120kb

input:

200 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

40000
792020000
319908096
286630939
515085548
95626140
472749362
800008042
594973486
139901984
847967250
125664877
254232250
419486325
204481923
979660340
41873095
540955890
585129047
205968776
196086667
674391130
737319172
669580034
973843015
207125612
331414909
119844754
24879477
990932807
8476927...

result:

ok 200 lines

Extra Test:

score: 0
Extra Test Passed