Acwing周赛26 C (简单dp都不会，建议/remake)

题目

题意: 询问长度为[l,r]的所有优秀字符串的个数.  优秀字符串: 首先是一个01字符串，可以将任意k个连续的1变成0，如果它最后可以变成全0，就是优秀字符串。

思路: 显然，全0串可以，恰好有k个、2*k个连续的1的串也可以。  考虑dp。(我还以为是计数题，推了半天公式过了样例，然后wa了。。。)  定义f[i]为长度为i的合法方案数。   f[i] = f[i-1] + f[i-k]. (分别对应最后一位为0，最后一位为1的状态转移)  前缀和维护f[i]即可，答案为s[r] - s[l-1]. tips: 由于要取模，二者作差后还要注意加上mod.

代码:

// Problem: 01串
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4081/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>T;
   // read(T);
   while(T--)
   {
   	 solve();
   }
   return 0;
}