国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

[BZOJ3142][Hnoi2013]數列(數學相關)

2019-11-11 04:56:31
字體:
來源:轉載
供稿:網友

題目描述

傳送門

題解

題意就是給出n,k,m,p,求有多少長度為k的序列A,滿足:首項為正整數;遞增數列;相鄰兩項的差小于等于m;最大值小于等于n 設a(i)=A(i+1)-A(i),我們只考慮a(i),顯然a(i)所需要滿足的條件就是ai≤m 一個合法的a(i)序列對答案的貢獻為 n?∑i=1k?1ai 合法的a(i)序列一共有mk?1個,那么 ans=∑a1=1m∑a2=1m...∑ak?1=1m(n?a1?a2?...?ak?1) =n?mk?1?∑a1=1m∑a2=1m...∑ak?1=1m∑i=1k?1ai 從這里可以看出,后面的一坨實際上就是1..m這些數每個數出現了(k?1)?mk?2次,求它們的和 所以用一下等差數列的求和公式?ans=n?mk?1?m(m+1)2?(k?1)?mk?2

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long longLL n,m,k,Mod,ans;LL fast_pow(LL a,LL p){ LL ans=1; for (;p;p>>=1,a=a*a%Mod) if (p&1) ans=ans*a%Mod; return ans;}void exgcd(LL a,LL b,LL &x,LL &y){ if (!b) x=1LL,y=0LL; else exgcd(b,a%b,y,x),y-=a/b*x;}LL inv(LL a,LL b){ LL x=0LL,y=0LL; exgcd(a,b,x,y); x=(x%b+b)%b; return x;}int main(){ scanf("%lld%lld%lld%lld",&n,&k,&m,&Mod); if (k==1) {
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 泌阳县| 河曲县| 霍邱县| 七台河市| 华安县| 绵竹市| 商城县| 静宁县| 宣城市| 海门市| 和硕县| 蒙城县| 白山市| 鄂尔多斯市| 东城区| 青州市| 汪清县| 鲁山县| 自治县| 文安县| 得荣县| 泊头市| 海阳市| 阳谷县| 巴南区| 保靖县| 从江县| 亳州市| 穆棱市| 井冈山市| 巴中市| 天全县| 波密县| 巴中市| 隆化县| 辉县市| 青神县| 田东县| 金乡县| 乌鲁木齐县| 渝中区|