传送门
虽然是远古时期的ctsc,但是果然还是ctsc啊
前置芝士:树状数组
这个题最开始的思路很好想,由于之前写过一个类似处理的题,所以这个题我一开始就想到了思路。
首先,我们可以尝试讲图腾表示为xxxx的形式
那么闪电就是:1324;高山是:1243和1432
ans=1324-1243-1432
然后应该容斥一下,但是我不会了。。
瞄一眼题解,我成功吧那个式子容斥出来了。
ans=1324-1243-1432
ans=(1x2x-1423)-(14xx-1423)-(12xx-1234)
ans=1x2x-14xx-12xx+1234
ans=1x2x-1xxx+13xx+1234
然后我就震惊的发现,我又不会了,这次变成仔细的研究题解了,各种讨论情况啊,nb啊,大佬们
下面的讨论情况还是看洛谷题解的吧,太难写了。题解传送门
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
#define lowbit(i) (i&(-i))
#define ls (get(a[i]))
#define rs (a[i]-1-ls)
#define lb (i-1-l[i])
#define rb (n-i-r[i])
const int mod=16777216,maxn=2e5+1;
int n,ans,a[maxn],f[maxn],now,l[maxn],r[maxn];
void add(int x,int y){for(rg int i=x;i<=n;i+=lowbit(i))(f[i]+=y)%=mod;}
int get(int x){int ans=0;for(rg int i=x;i;i-=lowbit(i))ans+=f[i];return ans;}
int C(int n,int m){return 1ll*n*(n-1)*(n-2)/6%mod;}
int main()
{
read(n);
for(rg int i=1;i<=n;i++)read(a[i]),l[i]=ls,r[i]=a[i]-1-l[i],add(a[i],1);
memset(f,0,sizeof f);
for(rg int i=1;i<=n;i++)
{
ans=((ans+(l[i]*(i-1)-get(a[i])-l[i]*(l[i]-1)/2)*rb)%mod+mod)%mod,
ans=((ans-C(rb,3))%mod+mod)%mod;
add(a[i],i);
}
memset(f,0,sizeof f);
for(rg int i=n;i;i--)ans=((ans+(1ll*get(a[i])-1ll*r[i]*(r[i]-1)/2)*rb)%mod+mod)%mod,add(a[i],a[i]-1);
memset(f,0,sizeof f);now=0;
for(rg int i=1;i<=n;i++)ans=(ans+1ll*rb*get(a[i]))%mod,add(a[i],l[i]);
printf("%d\n",ans);
}
bzoj1145[CTSC2008]图腾的更多相关文章
-
洛咕 P4528 [CTSC2008]图腾
洛咕 P4528 [CTSC2008]图腾 神题orz. 先约定abcd表示\(1\leq A<B<C<D\leq n\),而且\(y_a,y_b,y_c,y_d\)的排名正好是\( ...
-
Luogu4528 CTSC2008 图腾 树状数组、容斥
传送门 设$f_i$表示$i$排列的数量,其中$x$表示不确定 那么$$ans=f_{1324}-f_{1432}-f_{1243}=(f_{1x2x}-f_{1423})-(f_{14xx}-f_{ ...
-
bzoj AC倒序
Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...
-
[bzoj1145]图腾
如果将关系用一个数字来表示(相等表示不确定),那么题目相当于要计算$1324-1243-1432$=$(1323-1423)-(1233-1234)-(1322-1423)$=$1323+1234-( ...
-
BZOJ 1146: [CTSC2008]网络管理Network [树上带修改主席树]
1146: [CTSC2008]网络管理Network Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 3522 Solved: 1041[Submi ...
-
[BZOJ1146][CTSC2008]网络管理Network
[BZOJ1146][CTSC2008]网络管理Network 试题描述 M公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门.为了让分布在世界各地的N个 部门之间协同工作,公司搭建 ...
-
BZOJ 1143 1143: [CTSC2008]祭祀river 最长反链
1143: [CTSC2008]祭祀river Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动. ...
-
BZOJ 1146: [CTSC2008]网络管理Network 树链剖分+线段树+平衡树
1146: [CTSC2008]网络管理Network Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 870 Solved: 299[Submit] ...
-
BZOJ 1143: [CTSC2008]祭祀river 最长反链
1143: [CTSC2008]祭祀river Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline ...
随机推荐
-
time和datetime时间戳---python
time模块 time模块提供各种操作时间的函数 说明:一般有两种表示时间的方式: 1.时间戳的方式(相对于1970.1.1 00:00:00以秒计算的偏移量),时间戳是惟一的 2.以数 ...
-
pt-table-checksum和pt-heartbeat的使用
一.pt-table-checksum 1.主从上均新建账户GRANT SELECT, PROCESS, SUPER, REPLICATION SLAVE ON *.* TO 'checksum'@' ...
-
css2
CSS 实现div宽度根据内容自适应 <!DOCTYPE html> <html> <head> <meta charset="utf-8" ...
-
Asp.net mvc web api 在项目中的实际应用
Asp.net mvc web api 在项目中的实际应用 前言:以下只是记录本人在项目中的应用,而web api在数据传输方面有多种实现方式,具体可根据实际情况而定! 1:数据传输前的加密,以下用到 ...
-
LintCode-Fast Power
Calculate the an % b where a, b and n are all 32bit integers. Example For 231 % 3 = 2 For 1001000 % ...
-
C# 的轻量级 RPC 框架
Redola.Rpc 的一个小目标 Redola.Rpc 的一个小目标 Redola.Rpc 的一个小目标:20000 tps. Concurrency level: 8 threads Comple ...
-
基于Bootstrap设计网页
<%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding= ...
-
文件首行为空白行,为什么该行字符串长度为1(line.length()=1)
问题描述:最近编写程序遇到一个问题,文件首行的内容为空,但调用line0.length()返回的确为1 .如下图: 最初认为可能存在制表符,或者换行符的原因,于是调用了line0.trim();方法, ...
-
winform 实现类似于TrackBar的自定义滑动条,功能更全
功能很全,随便列几个 1.可以设置滑块的大小,边框颜色.背景色.形状等等吧 2.可以设置轨道的方向.边框颜色.背景色.阴影等等 ... 效果图: 下载链接https://download.csdn.n ...
-
C和C指针小记(一)-字符输入,函数,ASCII扩展表
1.连续接收输入字符时 int ch; while(ch != EOF && ch != '\n') ch 为什么被声明为整形,我们不是需要用它来读取字符的嘛? 因为:EOF是一个整形 ...