University Training Contest 6 整数拆分二

#include<iostream>#include<cstdio>#define NN 100005#define LL __int64#define mod 1000000007using namespace std;LL wu[NN],pa[NN];void init(){pa[0]=1;pa[1]=1;pa[2]=2;pa[3]=3;LL ca=0;for(LL i=1; i<=100000/2; i++){wu[ca++]=i*(3*i-1)/2;wu[ca++]=i*(3*i+1)/2;if(wu[ca-1]>100000) break;}for(LL i=4; i<=100000; i++){pa[i]=(pa[i-1]+pa[i-2])%mod;ca=1;while(wu[2*ca]<=i){if(ca&1){pa[i]=(pa[i]-pa[i-wu[2*ca]]);pa[i]=(pa[i]%mod+mod)%mod;if(wu[2*ca+1]<=i)pa[i]=(pa[i]-pa[i-wu[2*ca+1]]),pa[i]=(pa[i]%mod+mod)%mod;}else{pa[i]=(pa[i]+pa[i-wu[2*ca]]);pa[i]=(pa[i]%mod+mod)%mod;if(wu[2*ca+1]<=i)pa[i]=(pa[i]+pa[i-wu[2*ca+1]]),pa[i]=(pa[i]%mod+mod)%mod;}ca++;}}}LL work(int n,int k){LL ans=pa[n];LL ca=0;while(k*wu[2*ca]<=n){if(ca&1){ans=(ans+pa[n-k*wu[2*ca]]);ans=(ans%mod+mod)%mod;if(k*wu[2*ca+1]<=n)ans=(ans+pa[n-k*wu[2*ca+1]]),ans=(ans%mod+mod)%mod;}else{ans=(ans-pa[n-k*wu[2*ca]]);ans=(ans%mod+mod)%mod;if(k*wu[2*ca+1]<=n)ans=(ans-pa[n-k*wu[2*ca+1]]),ans=(ans%mod+mod)%mod;}ca++;}return ans;}int main(){int T,n,k;init();scanf("%d",&T);while(T–){scanf("%d%d",&n,&k);printf("%I64d\n",work(n,k));}return 0;}

，打掉的应是脆弱的铁屑，锻成的将是锋利的钢刀。