---
tags: Question tutorial
---

# C. 小青蛙的夢想
跟[無限階梯](http://203.64.191.163/ShowProblem?problemid=a650)很類似。
前進$a, b$階的方法數相加就好了。

### 轉移式

#### NA 20%
另$dp[i][j]\implies$ 在第`i`次抽卡且執行結束後在長度為$j$的方法數

{$$\displaystyle \begin{cases} dp[0][0] = 1\\dp[i][j] \equiv dp[i - 1][j -a ] + dp[i - 1][j - b]\;\;mod (10^9 + 7)\end{cases}$$
}
時間複雜度$O(NM)$
空間複雜度$O(NM)$

#### AC

空間複雜度在$N, M$都為$10^4$空間複雜度會爆掉。
所以需要把它改成滾動的。

#include <bits/stdc++.h>
using namespace std;

#define V vector
#define ll long long 
#define pii pair<int,int>
const int mod = 1e9 + 7;
int main () {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M;
	cin >> N >> M;
	V<V<int>> dp(2, V<int> (N, 0));
	dp[1][0] = 1; //dp[~0&1][0] = 1;
	for(int i = 0, a, b; i < M; i++) {
		cin >> a >> b;
		a %= N;
		b %= N;
		for(int j = 0; j < N; j++) {
			int cur_pos_a = (j - a + N) % N;
			int cur_pos_b = (j - b + N) % N;
			dp[i&1][j] = (dp[~i&1][cur_pos_a] + dp[~i&1][cur_pos_b]);
			dp[i&1][j] %= mod;
		}
	}
	cout << dp[~M&1][0] << endl;
}