走楼梯升级版(9.8 模拟赛。。。xxy原创）

走楼梯升级版

Description
在你成功地解决了上一道走楼梯后，xxy 不禁有些气恼，于是她又在楼梯上跳来跳
去，想要你求出她跳的方案数。..
xxy 站在一个 tot 阶楼梯下面，他每次可以往上跳 1—n 步，往下跳 1——m 步（由于地
心引力跳得比较远），而且在往下跳的时候只能踩在往上跳时踩过的格子。
现在 xxy 在楼梯上乱跳，想问她跳到楼梯顶上最后又跳回楼梯下面的方案数 mod
233333333。
注意：xxy 只能一直向上跳，跳到楼梯最上面，然后再往下跳，跳回楼梯最底下。
Input
一行 3 个整数 tot，n，m
Output
方案数 % 233333333
Example
Input
2
5 2 4
5 2 3
Output
52
42
Hint
10%的数据，1<=tot，n<=5,m=1
另外 10%的数据，1<=tot,n,m<=5
另外 20%的数据，1<=tot<=10000,1<=n,m<=5
另外 20%的数据，1<=tot<=10000,1<=n,m<=10
另外 20%的数据，1<=tot<=400000,1<=n,m<=5
对于 100%的数据，1<=tot<=400000,1<=n,m<=10

数据包：https://share.weiyun.com/f19ed2ee4716845a1b904cd89cb68016

将下楼看成上楼，dfs求出走1-m步的方案数和上下楼（即上楼两次）的方案数

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 #define LL long long
 9 #define maxn 400010
10 #define mod 233333333
11 
12 int n,m,tot,T;
13 LL f[maxn],a[maxn];
14 bool vis[maxn],vis1[maxn];
15 
16 inline void read(int &x)
17 {
18     int f=1; char c=getchar(); x=0;
19     while(c>'9'||c<'0') { if(c=='-') f*=-1; c=getchar(); }
20     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
21     x=x*f;
22 }
23 
24 int DFS_2(int x)
25 {
26     if(x==0) return 1;
27     int ans=0;
28     for(int i=1;i<=m;i++)
29     {
30         if(x-i<0) continue;
31         if(vis[x-i]&&!vis1[x-i])
32         {
33             vis1[x-i]=1;
34             ans+=DFS_2(x-i);
35             vis1[x-i]=0;
36         }
37     }
38     return ans;
39 }
40 
41 int DFS(int u,int limit)
42 {
43     if(u>limit) return 0;
44     if(u==limit) return 1;
45     int ans=0;
46     for(int i=1;i<=n;i++) ans+=DFS(u+i,limit);
47     return ans;
48 }
49 
50 
51 int DFS_1(int x,int limit)
52 {
53     if(x==limit) return DFS_2(limit);
54     int ans=0;
55     for(int i=1;i<=n;i++)
56     {
57         if(x+i>limit) continue ;
58         if(!vis[x+i])
59         {
60             vis[x+i]=1;
61             ans+=DFS_1(x+i,limit);
62             vis[x+i]=0;
63         }
64     }
65     return ans;
66 }
67 
68 inline void pre()
69 {
70     memset(vis,false,sizeof(vis));
71     memset(vis1,false,sizeof(vis1));
72     vis[0]=true;
73     for(int i=1;i<=m;i++) f[i]=(LL)DFS_1(0,i);
74     for(int i=1;i<=10;i++) a[i]=(LL)DFS(0,i);
75 }
76 
77 int main()
78 {
79     freopen("stair.in","r",stdin);
80     freopen("stair.out","w",stdout);
81     read(T);
82     while(T--)
83     {
84         read(tot); read(n); read(m);
85         pre();
86         for(int i=m+1;i<=tot;i++)
87         {
88             f[i]=0;
89             for(int j=1;j<=m;j++)
90                 f[i]=(f[i]+(f[i-j]*a[j]))%mod;
91         }
92         printf("%I64d
",f[tot]);
93     }
94     return 0;
95 }

View Code