思维。
暴力的话是会超时的,但也可以骗点分。 (采用差分数组暴力)
讲一下AC思路。
统计出来每个前缀和取模 k k k后结果的个数,比如 c n t [ 0 ] cnt[0] cnt[0] 表示前缀和取模 k k k 等于 0 0 0 的前缀个数; c n t [ 1 ] cnt[1] cnt[1] 表示前缀和取模 k k k 等于 1 1 1 的前缀个数;……
假设前缀和取模 k k k等于 1 1 1的全部前缀如下:
总共三个前缀,我们考虑任选其中的两个前缀,长前缀比短前缀多出的部分的数是否可以保证求和取模
k
k
k等于
0
0
0?
假设短前缀和为 S u m s h o r t Sum_{short} Sumshort,长前缀和为 S u m l o n g Sum_{long} Sumlong, S u m l o n g − S u m s h o r t Sum_{long}-Sum_{short} Sumlong−Sumshort 为长前缀比短前缀多出的部分的数之和。
( S u m l o n g − S u m s h o r t ) % k = S u m l o n g % k − S u m s h o r t % k = 1 − 1 = 0 (Sum_{long}-Sum_{short})\%k=Sum_{long}\%k-Sum_{short}\%k=1-1=0 (Sumlong−Sumshort)%k=Sumlong%k−Sumshort%k=1−1=0
所以长前缀比短前缀多出的部分的数就是满足条件的一组数。如此一来,我们可以只需要在这三个前缀中选两个构成一组满足条件的数,即 C 3 2 C_3^2 C32 为前缀和取模为 1 1 1 的前缀能构成取模 k k k 等于 0 0 0 的序列的方案数。
特殊地,对于前缀和取模 k k k为 0 0 0的前缀能组合出满足条件的序列的个数还需要加上它们自己,也就是我们可以把每一个满足前缀和取模 k k k为 0 0 0的前缀单拎出来,它们还是满足和取模为 0 0 0的要求,因此,还要将这些方案加上。
在代码实现上,我们只需要将 c n t [ 0 ] cnt[0] cnt[0] 初始化为 1 1 1 即可,因为 C n + 1 2 = C n 2 + n C_{n+1}^{2} = C_{n}^{2} + n Cn+12=Cn2+n
代码#include
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL n, k, a, s, cnt[N], ans;
int main()
{
cin >> n >> k;
cnt[0] = 1;
for (int i = 1;i > a;
s += a;
cnt[s % k] ++;
}
for (int i = 0;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?