当前位置:网站首页>CF1548C The Three Little Pigs

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\))


Why? dp What about ?

Make \(dp[x][m]=\sum\limits_{i=0}^{n - 1} C_{3i+m}^x(m = 0,1,2)\). that \(ans[x] = dp[x][0]+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][0]+dp[x][1]+dp[x][2] = C_{3n}^{x+1} \ \ (1)\).

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

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

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

 

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

 

The boundary conditions :\(dp[0][0] = dp[0][1] = dp[0][2] = 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;
In ll read()
{
	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][3], 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[0] = inv[0] = 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[0][0] = dp[0][1] = dp[0][2] = n;
	for(int i = 1; i <= m; ++i)
	{
		ll c = C(m, i + 1);
		dp[i][0] = ADD(ADD(c, mod - dp[i - 1][0] * 2 % mod), mod - dp[i - 1][1]) * inv3 % mod;
		dp[i][1] = ADD(ADD(c, dp[i - 1][0]), mod - dp[i - 1][1]) * inv3 % mod;
		dp[i][2] = ADD(ADD(c, dp[i - 1][0]), dp[i - 1][1] * 2 % mod) * inv3 % mod;
	}
}

int main()
{
	n = read(), Q = read(); m = n * 3;
	init();
	for(int i = 1; i <= Q; ++i)
	{
		int x = read();
		write(ADD(dp[x][0], C(m, x))), enter;
	}
	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.
 
 
 
 

版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808003020480Q.html

随机推荐