Planar Reflections

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define db double
 4 using namespace std;
 5 ll mod=1e9+7;
 6 const int qs=1e3+7;
 7 ll t,n,k,f[qs][qs];
 8 //f[i][j] 表示前面还有i块墙,当前能量为j 产生的粒子数 
 9 //f[i-1][j]:粒子向前走,能量不变
10 //f[n-i][j-1]:分裂出的粒子向相反方向走,能量-1 
11 int main(){
12     std::ios::sync_with_stdio(false);
13     cin>>t;
14     while(t--){
15         cin>>n>>k;
16         for(int i=1;i<=n;++i)  f[i][1]=1; //能量为1结果恒为1 
17         for(int j=1;j<=k;++j)  f[0][j]=1; //没有墙粒子数为1
18         for(int j=1;j<=k;++j){
19             for(int i=1;i<=n;++i){
20                 f[i][j]=(f[i-1][j]+f[n-i][j-1])%mod;
21             }
22         }
23         cout<<f[n][k]<<"\n";    
24     }
25     
26     
27     return 0;
28 }