函数变化
考试最后关头，我才发现T1是有规律的，哭~
写下一个暴力程序，打表后，你可以发现前n-1项中第i项的答案为\(2^{i-1}\)，第n项为\(2^{n-1}-1\)，n以后项的答案为前n项的和，就可以\(O(n)\)解决问题了。
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=1e6+5;
const int mod=1e9+9;
ll n,m,f[N];
int main()
{
n=read(),m=read();
ll sum=1;f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[i-1]*2%mod;
if(i==n)f[i]-=1;
sum=(sum+f[i])%mod;
}
for(int i=n+1;i<=m;i++)
{
f[i]=sum;
sum=((sum-f[i-n]+f[i])%mod+mod)%mod;
}
printf("%lld\n",f[m]);
return 0;
}