1498C. Planar Reflections
C. Planar Reflections time limit per test1 second memory limit per
test256 megabytes inputstandard input outputstandard output Gaurang
has grown up in a mystical universe. He is faced by n consecutive 2D
planes. He shoots a particle of decay age k at the planes.A particle can pass through a plane directly, however, every plane
produces an identical copy of the particle going in the opposite
direction with a decay age k−1. If a particle has decay age equal to
1, it will NOT produce a copy.For example, if there are two planes and a particle is shot with decay
age 3 (towards the right), the process is as follows: (here, D(x)
refers to a single particle with decay age x)the first plane produces a D(2) to the left and lets D(3) continue on
to the right; the second plane produces a D(2) to the left and lets
D(3) continue on to the right; the first plane lets D(2) continue on
to the left and produces a D(1) to the right; the second plane lets
D(1) continue on to the right (D(1) cannot produce any copies). In
total, the final multiset S of particles is {D(3),D(2),D(2),D(1)}.
(See notes for visual explanation of this test case.)Gaurang is unable to cope up with the complexity of this situation
when the number of planes is too large. Help Gaurang find the size of
the multiset S, given n and k.Since the size of the multiset can be very large, you have to output
it modulo 109+7.Note: Particles can go back and forth between the planes without
colliding with each other.Input The first line of the input contains the number of test cases t
(1≤t≤100). Then, t lines follow, each containing two integers n and k
(1≤n,k≤1000).Additionally, the sum of n over all test cases will not exceed 1000,
and the sum of k over all test cases will not exceed 1000. All test
cases in one test are different.Output Output t integers. The i-th of them should be equal to the
answer to the i-th test case.Examples inputCopy 4 2 3 2 2 3 1 1 3 outputCopy 4 3 1 2 inputCopy 3 1
1 1 500 500 250 outputCopy 1 2 257950823 Note Let us explain the first
example with four test cases.Test case 1: (n=2, k=3) is already explained in the problem statement.
See the below figure of this simulation. Each straight line with a
different color represents the path of a different particle. As you
can see, there are four distinct particles in the multiset. Note that
the vertical spacing between reflected particles is for visual clarity
only (as mentioned before, no two distinct particles collide with each
other)
一个粒子每撞到一个隔板就出现一个它的衰变粒子并且保留它本身。
相对来说 记忆化搜索的方法最容易理解
//cyc
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define vector<int> VI
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mst(a) memset(a,0,sizeof a)
using namespace std;
typedef pair<int,int> pii;
const int mod=1e9+7;
int dp[1005][1005][2];
int n,m;
int solve(int n1,int k1,int lr)//n位置 k1剩余衰变次数 lr左右方向(0左1右）
{
if(k1==1)return 1;
if(dp[n1][k1][lr]!=0){
return dp[n1][k1][lr];
}
int ans=2;
if(lr==1){
if(n1>1){
ans+=solve(n1-1,k1-1,lr-1)-1;//异方向 剩余衰变次数-1
ans%=mod;
}
if(n1<n){
ans+=solve(n1+1,k1,lr)-1; //同方向 直接前进到下一个隔板
ans%=mod;
}
}
else{
if(n1>1){
ans+=solve(n1-1,k1,lr)-1;
ans%=mod;
}
if(n1<n){
ans+=solve(n1+1,k1-1,lr+1)-1;
ans%=mod;
}
}
return dp[n1][k1][lr]=ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _;
cin>>_;
while(_--){
cin>>n>>m;
mst(dp);
cout<<solve(1,m,1)<<endl;//从1开始 剩余m次 向右
}
}
另外的dp方法，感觉这个递推式有些难想
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[1010][1010];
int main()
{
int T;cin>>T;while(T--)
{
int n,k;cin>>k>>n;
for(int i=0;i<=k;i++)f[1][i]=1;//只剩下1次衰变粒子数必为1
for(int i=2;i<=n;i++){
f[i][0]=1;//没有隔板时粒子数必为1
for(int j=1;j<=k;j++)
f[i][j]=(f[i-1][k-j]+f[i][j-1])%mod;//i个隔板已进行j次衰变时
//这个点具有的粒子总量等于
//上个点已衰变(k-j)次与这个点已衰变(j-1)次的和
}
cout<<f[n][k]<<"\n";
}
}