Wechat steps
Problem solution
Now I've only filled in the question one year ago.
First, we consider a simple violence. However, I didn't even expect this violence in the examination room
Let's transform how many steps a point can take, and look at it as a whole.
We consider how many points can survive after taking this step, that is, we don't go out of the whole grid.
Obviously, each dimension is independent in the surviving length if the second dimension
i
i
The length of our survival in dimension i is
l
e
n
i
len_{i}
leni, so our total number of surviving grids is
∏
i
=
1
k
l
e
n
i
\prod_{i=1}^{k}len_{i}
∏i=1kleni. Obviously, all the surviving points are continuous polyhedrons, and we can multiply them to get the total answer.
We consider that for this one dimension, our survival interval is
[
L
i
,
R
i
]
[L_{i},R_{i}]
[Li, Ri], then our movement is equivalent to making our interval become
[
L
i
+
x
,
R
i
+
x
]
[L_{i}+x,R_{i}+x]
[Li+x,Ri+x].
If part of the range exceeds US after this movement
[
1
,
w
i
]
[1,w_{i}]
If [1,wi] is limited, then this part of the interval should obviously be deleted, and the surviving interval becomes
[
max
(
1
,
L
i
+
x
)
,
min
(
w
i
,
R
i
+
x
)
]
[\max(1,L_{i}+x),\min(w_{i},R_{i}+x)]
[max(1,Li+x),min(wi,Ri+x)].
Our new
l
e
n
i
len_{i}
leni ， that's it
min
(
w
i
,
R
i
+
x
)
−
max
(
1
,
L
i
+
x
)
+
1
\min(w_{i},R_{i}+x)-\max(1,L_{i}+x)+1
min(wi,Ri+x)−max(1,Li+x)+1.
In this way, we only need to change the length of our operation each time.
Obviously, the time complexity of such violence is
O
(
n
max
(
w
i
)
)
O\left(n\max(w_{i})\right)
O(nmax(wi)), probably
30
p
t
s
30pts
30pts.
But obviously, the above process can be optimized.
Since there was no template at the beginning of our first round of operation, the movement of the first round was irregular with that of other rounds. We remember it in the first round
i
i
The length after the change caused by i-dimensional movement is
a
i
a_{i}
ai.
After that, the change brought by each round is fixed. We remember that it makes our length change as
b
i
b_{i}
bi.
Obviously, the next day
i
+
1
i+1
After i+1 round of movement, our second
j
j
The remaining length of dimension j is
a
j
−
i
b
j
a_{j}-ib_{j}
aj−ibj.
Why don't we record the second time
2
2
Front of each round after 2 rounds
i
i
Step i can help us
j
j
The influence of j dimension is
f
i
,
j
f_{i,j}
fi,j.
In this way, we can know our second
i
i
Round i
j
j
The size of j times.
We assume that a total of
T
+
2
T+2
T+2 round, then from
2
2
The contribution from the beginning of round 2 is,
∑
x
=
0
T
∑
i
=
1
n
∏
j
=
1
k
(
a
j
−
x
b
j
−
f
i
,
j
)
=
∑
i
=
1
n
∑
x
=
0
T
∏
j
=
1
k
(
a
j
−
x
b
j
−
f
i
,
j
)
\sum_{x=0}^{T}\sum_{i=1}^{n}\prod_{j=1}^{k}(a_{j}-xb_{j}-f_{i,j})=\sum_{i=1}^{n}\sum_{x=0}^{T}\prod_{j=1}^{k}(a_{j}-xb_{j}-f_{i,j})
x=0∑Ti=1∑nj=1∏k(aj−xbj−fi,j)=i=1∑nx=0∑Tj=1∏k(aj−xbj−fi,j)
Then we can put the back
∏
j
=
1
k
(
a
j
−
x
b
j
−
f
i
,
j
)
\prod_{j=1}^{k}(a_{j}-xb_{j}-f_{i,j})
Π j=1k (aj − xbj − fi,j) is regarded as a
x
x
x
k
k
k-degree polynomial, for all
i
∈
[
0
,
k
]
i\in [0,k]
i ∈ [0,k], find its coefficient and multiply it by
∑
x
=
0
T
x
i
\sum_{x=0}^{T}x^i
∑x=0Txi.
The previous coefficient can obviously be passed
O
(
k
2
)
O\left(k^2\right)
The knapsack of O(k2) is calculated and multiplied directly by polynomial.
hinder
∑
x
=
0
T
x
i
\sum_{x=0}^{T}x^i
∑x=0Txi，
T
T
T is obviously
min
j
=
1
k
⌈
a
j
−
f
i
,
j
b
j
−
1
⌉
\min_{j=1}^{k}\lceil\frac{a_{j}-f_{i,j}}{b_{j}}-1\rceil
minj=1k ⌈ bj ⌈ aj − fi,j − 1 ⌉ and
∑
x
=
0
T
x
i
\sum_{x=0}^{T}x^i
∑ x=0T ∑ xi can be obtained by Stirling inversion.
because
n
m
=
∑
k
=
0
m
{
m
k
}
n
k
‾
n^m=\sum_{k=0}^{m}{m\brace k}n^{\underline k}
nm=∑k=0m{km}nk，
So there are
∑
x
=
0
T
x
i
=
∑
x
=
0
T
∑
k
=
0
i
{
i
k
}
x
k
‾
=
∑
k
=
0
i
{
i
k
}
∑
x
=
0
T
x
k
‾
=
∑
k
=
0
i
{
i
k
}
k
!
∑
x
=
0
T
(
x
k
)
=
∑
k
=
0
i
{
i
k
}
k
!
(
T
+
1
k
+
1
)
\sum_{x=0}^{T}x^i=\sum_{x=0}^{T}\sum_{k=0}^{i}{i\brace k}x^{\underline k}=\sum_{k=0}^{i}{i\brace k}\sum_{x=0}^{T}x^{\underline k}=\sum_{k=0}^{i}{i \brace k}k!\sum_{x=0}^{T}\binom{x}{k}=\sum_{k=0}^{i}{i\brace k}k!\binom{T+1}{k+1}
x=0∑Txi=x=0∑Tk=0∑i{ki}xk=k=0∑i{ki}x=0∑Txk=k=0∑i{ki}k!x=0∑T(kx)=k=0∑i{ki}k!(k+1T+1)
Obviously, this thing can
O
(
k
)
O\left(k\right)
O(k), a very classic formula.
We're going to
i
∈
[
0
,
k
]
i\in[0,k]
i ∈ [0,k] has to calculate a formula on the right. Obviously, this part is also
O
(
k
2
)
O\left(k^2\right)
O(k2).
So the time complexity is
O
(
n
k
2
)
O\left(nk^2\right)
O(nk2) is OK.
But we can still continue to optimize, the previous
∏
j
=
1
k
(
a
j
−
x
b
j
−
f
i
,
j
)
\prod_{j=1}^{k}(a_{j}-xb_{j}-f_{i,j})
Π j=1k (aj − xbj − fi,j) can be divided and treated
N
T
T
NTT
NTT or
M
T
T
MTT
MTT or
k
a
r
a
t
s
u
b
a
karatsuba
karatsuba multiplication.
And the back
∑
x
=
0
T
x
i
\sum_{x=0}^{T}x^i
Σ x=0T xi due to
T
T
There are only two values of T, which can be preprocessed.
So the time complexity becomes
O
(
n
k
log
2
k
o
r
n
k
k
)
O\left(nk\log^2k \, or\,nk\sqrt{k}\right)
O(nklog2kornkk
) Yes, although I don't think anyone will fight like this.
Source code
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int n,k,a[15],b[15],w[15],l[15],r[15],f[MAXN][15],c[MAXN],d[MAXN],ans,dp[15];
int fac[MAXN],ff[MAXN],S[15][15];
void init(){
fac[0]=fac[1]=ff[1]=1;
for(int i=2;i<=k+1;i++)
fac[i]=1ll*i*fac[i-1]%mo,
ff[i]=1ll*(mo-mo/i)*ff[mo%i]%mo;
S[0][0]=1;
for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)
S[i][j]=add(S[i-1][j-1],1ll*j*S[i-1][j]%mo,mo);
}
signed main(){
read(n);read(k);ans=1;init();
for(int i=1;i<=k;i++)read(w[i]),l[i]=1,r[i]=w[i],ans=1ll*ans*w[i]%mo;
for(int i=1;i<=n;i++){
read(c[i]);read(d[i]);l[c[i]]+=d[i];r[c[i]]+=d[i];
l[c[i]]=max(l[c[i]],1);r[c[i]]=min(r[c[i]],w[c[i]]);
int summ=1;for(int j=1;j<=k;j++)summ=1ll*summ*(r[j]-l[j]+1)%mo;
ans=add(summ,ans,mo);
if(l[c[i]]>r[c[i]]){printf("%d\n",ans);return 0;}
}
for(int i=1;i<=k;i++)a[i]=r[i]-l[i]+1;int sum=0;
for(int i=1;i<=n;i++){
l[c[i]]+=d[i];r[c[i]]+=d[i];
l[c[i]]=max(l[c[i]],1);r[c[i]]=min(r[c[i]],w[c[i]]);
int summ=1;for(int j=1;j<=k;j++)summ=1ll*summ*(r[j]-l[j]+1)%mo;
sum=add(summ,sum,mo);
if(l[c[i]]>r[c[i]]){printf("%d\n",add(sum,ans,mo));return 0;}
for(int j=1;j<=k;j++)f[i][j]=a[j]-(r[j]-l[j]+1);
}
for(int i=1;i<=k;i++)b[i]=f[n][i];bool flag=0;
for(int i=1;i<=k;i++)flag|=(b[i]!=0);
if(!flag){puts("-1");return 0;}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++)dp[j]=0;dp[0]=1;
for(int j=1;j<=k;j++){
for(int k=j;k>0;k--)
dp[k]=add(1ll*(a[j]-f[i][j])*dp[k]%mo,1ll*(mo-b[j])*dp[k-1]%mo,mo);
dp[0]=1ll*(a[j]-f[i][j])*dp[0]%mo;
}
int T=INF;
for(int j=1;j<=k;j++)if(b[j])T=min(T,(a[j]-f[i][j])/b[j]);
for(int j=0;j<=k;j++){
int tmp=1,num=0;
for(int l=0;l<=k;l++)
tmp=1ll*(T+1-l)*ff[l+1]%mo*tmp%mo,
Add(num,1ll*S[j][l]*fac[l]%mo*tmp%mo,mo);
Add(ans,1ll*num*dp[j]%mo,mo);
}
}
printf("%d\n",ans);
return 0;
}