A.函数变换
-
花了两个小时试图使用排列组合解决，然而最后发现居然是个结论题……
-
我果然是和结论题有仇吧
Solution
- 打个表，就能发现当 \(n\) 确定时，\(ans_m\) 的值有公式可推：
- 当 \(1\le i<m\) 时，\(ans_i=2^{i-1}\)；
- 当 \(i\ge m\) 时，\(ans_i=\sum\limits_{j=i-m}^{i-1} ans_j\)；
AC code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod=1e9+9;
#define ll long long
#define re register
int n,m;
ll mul[N<<1];
ll ans=0;
int main(){
// freopen("change.in","r",stdin);
// freopen("change.out","w",stdout);
scanf("%d%d",&m,&n);
if(m==1){
printf("%d",0);
return 0;
}
mul[0]=0;
mul[1]=1;
for(int i=2;i<m;++i)
mul[i]=(1ll*mul[i-1]*2)%mod;
if(n<m){
printf("%d",mul[n]);
return 0;
}
for(int i=1;i<=m;++i)
(mul[i]+=mul[i-1])%=mod;
for(int i=m;i<=n;++i){
(mul[i]=(mul[i-1]-mul[i-m-1])%mod+mod)%=mod;
(mul[i]+=mul[i-1])%=mod;
}
printf("%lld",((mul[n-1]-mul[n-m-1])%mod+mod)%mod);
return 0;
}
B.刺客信条
- 这美妙的名字，这美妙的题目背景……；
Solution
- 二分答案 + 并查集；