UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203551#3566. T1GS128100171ms3908kbC++111.6kb2024-02-27 14:09:212024-02-27 14:09:23

answer

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef long double LD;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plll;
typedef pair<int,int> pii;

const ll MOD=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
const LD eps=1e-9;

inline ll read()
{
	ll ans=0, f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') ans=ans*10+c-'0', c=getchar();
	return ans*f;
}

inline ll qpow(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y&1) res=(res*x)%MOD;
		x=(x*x)%MOD;
		y>>=1;
	}
	return res;
}

const int N=1e5+500;

inline bool gett(int x,int y)
{
	return x&(1<<y);
}

int n, m=0;
int w[N];

ll ans=0;
ll f[N][2], pre[N];

void init()
{
	n=read();
	for(int i=1;i<=n;i++) w[i]=read();
	return ;
}

void solve()
{
	int s, tag;
	ll x, y;
	for(int i=30;i>=0;i--)
	{
		s=(1<<i)-1, tag=0;
		pre[0]=1;
		f[n+1][1]=0;
		f[n+1][0]=1;
		
		for(int j=1;j<=n;j++)
		{
			pre[j]=(w[j]&s)+1;
			if(gett(w[j],i))f[j][1]=(w[j]&s)+1, f[j][0]=s+1;
			else f[j][0]=(w[j]&s)+1, f[j][1]=0;
			pre[j]%=MOD ,f[j][0]%=MOD, f[j][1]%=MOD;
		}
		
		for(int j=2;j<=n;j++) pre[j]=(pre[j-1]*pre[j])%MOD;
		
		for(int j=n-1;j>=1;j--)
		{
			x=f[j][0], y=f[j][1];
			f[j][0]=(f[j+1][0]*x+f[j+1][1]*y)%MOD;
			f[j][1]=(f[j+1][0]*y+f[j+1][1]*x)%MOD;
		}
		
		for(int j=1;j<=n;j++)
		{
			if(gett(w[j],i)) ans=(ans+(pre[j-1]*f[j+1][tag]))%MOD, tag^=1;
		}
		
		if(tag) break;
		if(i==0) ans++;
	}
	
	cout<<ans;
	return ;
}

int main()
{
	init();
	solve();
	
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

10
3 5 0 1 0 3 5 4 2 5

output:

13248

result:

ok 1 number(s): "13248"

Subtask #2:

score: 10
Accepted

Test #2:

score: 10
Accepted
time: 56ms
memory: 3904kb

input:

100000
25 0 7 1 42 27 29 17 26 23 11 4 24 40 31 10 6 16 26 26 46 27 7 32 9 33 17 15 4 44 36 29 19 17...

output:

460821675

result:

ok 1 number(s): "460821675"

Subtask #3:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 52ms
memory: 3908kb

input:

100000
14 25 9 27 9 33 48 28 10 29 28 39 50 33 8 18 38 0 34 25 13 7 30 48 13 39 14 11 40 8 32 3 7 16...

output:

885189946

result:

ok 1 number(s): "885189946"

Subtask #4:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 11ms
memory: 3904kb

input:

100000
999998102 402961903 309346107 445160702 274308544 145846539 341002420 77841978 313436667 3206...

output:

714756233

result:

ok 1 number(s): "714756233"

Subtask #5:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 13ms
memory: 3904kb

input:

100000
999998479 400795186 127605328 439009686 279338791 222344190 32214702 347490239 390113609 1737...

output:

885251777

result:

ok 1 number(s): "885251777"

Subtask #6:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 9ms
memory: 3908kb

input:

100000
999980995 341927799 474797020 355936070 215296904 77682610 413850993 194378088 233473841 3566...

output:

99729538

result:

ok 1 number(s): "99729538"

Subtask #7:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 0ms
memory: 1224kb

input:

2000
540706819 309629779 17707890 194083691 334726587 456162964 498417390 246765617 957682339 604730...

output:

800177499

result:

ok 1 number(s): "800177499"

Subtask #8:

score: 10
Accepted

Test #8:

score: 10
Accepted
time: 1ms
memory: 1224kb

input:

2000
101722906 988313572 550840902 777765553 778991206 95817204 989809443 357040014 425595004 794587...

output:

443206431

result:

ok 1 number(s): "443206431"

Subtask #9:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 13ms
memory: 3908kb

input:

100000
327468559 836395032 98737045 14714567 147268924 355455125 829199457 117664948 79547712 117935...

output:

252529800

result:

ok 1 number(s): "252529800"

Subtask #10:

score: 10
Accepted

Test #10:

score: 10
Accepted
time: 16ms
memory: 3904kb

input:

100000
334373908 573410989 584461609 757523993 595819683 93095595 866600961 552146722 657326632 1804...

output:

633437866

result:

ok 1 number(s): "633437866"