D-碎碎念 Generating Function分析

最近，遇到数数题目，总是先想到生成函数哈

每AC一道题目，要么喊1次，要么喊次，设为AC一道题目的生成函数，

整个竞赛过程，是一个AC的“序列”: 外加最后的一个可能不AC的“题目” ， 所以整体的生成函数是：

亦即：， 这里的比较简单，可得递归关系

一般性问题 已知求，可用二分FFT DP来解决 （赛时脑热，没理递归关系，直接二分DP练手了哈）

简单代码：

#include<stdio.h>
#define MOD 1000000007
int dp[100004];
int ss[100004];
int main() {
	int n, i, x, q, a, b, r;
	scanf("%d", &x);
	for (i=0; i<=100000; i++) {
		if (i==0) dp[i]=1;
		else if (i==x) dp[i]=(1+dp[i-1])%MOD;
		else dp[i]=((i>=1?dp[i-1]:0)+(i>=x+1?dp[i-x-1]:0))%MOD;
	}
	//prefix sum
	ss[0]=0; for (i=0; i<=100000; i++) ss[i+1]=(ss[i]+dp[i])%MOD;
	scanf("%d", &q); while(q--) {
		scanf("%d %d", &a, &b);
		r=ss[b+1]-ss[a];
		if (r<0) r+=MOD;
		printf("%d\n", r);
	}

	return 0;
}