赛时写了一个很老实的循环,果不其然T了.这时候基础不牢就地动山摇啊,硬是没想出来巧解,还是赛后去研究的,哎.
考虑到位与运算的特性,将样例化为二进制来分析:
根据题意计算,以右起第一列为例,第一个1与所有的1位与得到3,第二个1与所有的1位与也得到3....就这样得到了3个3也就是9.显然,对于数据中所有整数的第i位,运算结果就是1的个数的平方.
即,设有t[i]个数在二进制下的第i位为1,那么答案就会累加t2[i]个二进制下的1.所以就转化为了求:
因为答案以十进制输出,所以最后还要按位权乘2的i次幂转回10进制.
给定平面上n个点的坐标并且我们定义两个点的距离为曼哈顿距离.曼哈顿距离是指对两个点(x1y1)他们之间的距离为∣x2−x1∣+∣y2−y1∣.
众所周知三个点可以构成一个三角形那么n个点可以构成C(n3) 个三角形现在你需要求出所有三角形的周长和.输出在模998244353意义下的答案.数据保证不存在三点共线.
第一行一个整数表示n.
接下来n行每行两个整数xy表示一个点.
这题其实就是一道纯思维题. 真的差一点点就A了,死在草稿纸太乱,哎,还是人菜了.
假设有5个点,编号为12345.根据组合数原理,一共有以下几种组合:
两点连成一条边,那么1-2就是第一条边,可以很清晰的看见一共计算了3次1-2边.事实上,每一条边都算了三次,这很容易数出来.
那么不难总结出:对任意的n个点,他们两两连成的边在这道题里会被计算n-2次.这就是答案.
值得一提的是,这题的点要用LL来存,不然只能过60%.题目里明明白白给出来的1e9怎么就不作数了呢,真是奇怪.
有一款自走棋有26种操作每种操作我们都用abcd...xyz的符号来代替.
现在牛牛有一个长度为n的操作序列他现在可以从里面拿出某些操作来组合成一个操作视频 比如说操作序列是abcd那么操作视频就有abcdabacad等(也就是操作序列的子序列).他现在想知道长度为k且本质不同的操作视频有多少种.
比如对于abab,长度为2且本质不同的结果有abaababb.
考虑到答案可能非常大你只需要输出在模1e9+7意义下的答案就可以了.
第一行两个整数nk.(1<=n<=1e3 0<=k<=n)
第二行一个长度为n的字符串保证只存在小写字母.
一行一个整数表示长度为k且本质不同的操作视频的个数.
题目就是求长度为k的所有本质不同子序列,很容易可以想到dp.
很有趣的是,这题存在一个k为0的点,可以特判一手.