# CF1548C The Three Little Pigs

2021-08-08 00:31:01 mrclr

delivery

The solution of this problem is wonderful , Although it is dp, But from beginning to end, no step was within my expectation ……

One sentence question ： Give me a $$n$$,$$q$$ Group inquiry , Every time I ask $$\sum_{i=1}^{n} C_{3i}^x \ \ \textrm{mod} \ \ 10^9+7$$.（$$1 \leqslant n \leqslant 10^6, 1 \leqslant q \leqslant 2 * 10^5$$）

Make $$dp[x][m]=\sum\limits_{i=0}^{n - 1} C_{3i+m}^x(m = 0,1,2)$$. that $$ans[x] = dp[x]+C_{3n}^x$$.

and $$\sum\limits_{m=0}^2dp[x][m]=\sum\limits_{i=0}^{n-1}(C_{3i}^x+C_{3i+1}^x+C_{3i+2}^x)=\sum\limits_{i=0}^{3n-1}C_i^x$$. Because the sum of these three terms is equivalent to all $$i\in[1,3n-1]$$ All visited .

Next , according to  $$\textrm{Hockey-Stick Identity}$$, Yes $$\sum\limits_{i=0}^{3n-1}C_i^x = C_{3n}^{x+1}$$.（ In fact, this step is OK if you don't know , Just preprocess it out ）

So there is $$dp[x]+dp[x]+dp[x] = C_{3n}^{x+1} \ \ (1)$$.

According to Yang Hui's triangle , Can we get the relationship ：
$$dp[x] = dp[x]+dp[x - 1] \ \ (2)$$,

$$dp[x] = dp[x] + dp[x - 1] \ \ (3)$$.

The final will be $$(1)(2)(3)$$ To unite , You can solve the recursive formula

\begin{align*} dp[x] &= \frac1{3}(C_{3n}^{x+1} - 2dp[x-1] - dp[x - 1]) \\ dp[x] &= \frac1{3}(C_{3n}^{x+1} + dp[x-1] - dp[x - 1]) \\ dp[x] &= \frac1{3}(C_{3n}^{x+1} + dp[x-1] + 2dp[x - 1]) \end{align*}

The boundary conditions ：$$dp = dp = dp = 0$$.

Time complexity $$O(n+q)$$.

It's wonderful .

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 3e6 + 5;
const ll mod = 1e9 + 7;
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}

In ll ADD(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}

int n, m, Q;

ll f[maxn], inv[maxn], dp[maxn], inv3;
In ll C(int n, int m) {return f[n] * inv[m] % mod * inv[n - m] % mod;}
In void init()
{
inv3 = quickpow(3, mod - 2);
f = inv = 1;
for(int i = 1; i <= m; ++i) f[i] = f[i - 1] * i % mod;
inv[m] = quickpow(f[m], mod - 2);
for(int i = m - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
dp = dp = dp = n;
for(int i = 1; i <= m; ++i)
{
ll c = C(m, i + 1);
dp[i] = ADD(ADD(c, mod - dp[i - 1] * 2 % mod), mod - dp[i - 1]) * inv3 % mod;
dp[i] = ADD(ADD(c, dp[i - 1]), mod - dp[i - 1]) * inv3 % mod;
dp[i] = ADD(ADD(c, dp[i - 1]), dp[i - 1] * 2 % mod) * inv3 % mod;
}
}

int main()
{
init();
for(int i = 1; i <= Q; ++i)
{
}
return 0;
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.


https://chowdera.com/2021/08/20210808003020480Q.html