2122. 幸运票

(File IO): input:tickets.in output:tickets.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述

给你一个数N(1<=N<=50),每张票有2N位,同时给你这2N位上的和S,如果这张票的前N位的和等于后N位的和,那我们称这张票是吉祥的,每一位可以取0-9。

你的任务是计算吉祥票的总数。

输入

输入N和S,S是所以位上的和,假设S<=1000

输出

输出吉祥票的总数

样例输入

2 2

样例输出

数据范围限制

见题目描述

Solution

此题很不友好……emmm……

Algorithm1

死命dfs

Code1

1 #pragma GCC optimize(2) 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #define IL inline12 using namespace std;13 14 unsigned long long n,s,ans,sum;15 IL void dfs(unsigned long long depth,unsigned long long now,unsigned long long sum)16 {17 if(sum*2>s) return;18 if(depth==n){19 if(sum==s/2)20 ans++;21 return;22 }23 for(int i=0;i<10;i++)24 {25 dfs(depth+1,now*10+i,sum+i);26 }27 }28 int main()29 {30 // freopen("tickets.in","r",stdin);31 // freopen("tickets.out","w",stdout);32 cin>>n>>s;33 dfs(0,0,0);34 cout<

Code1

Algorithm2

打了一番表，发现真相……

一个斜着的杨辉三角形*2？？？

由于某些原因（换了电脑且插不了U盘）

没法详细的讲规律

这是ans，不是ans的平方！

0 0 0 0 0 0 0 0……
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 0 ……
1 1 3 3 6 6 10 10 15 15 21 21 28 28 36 36 45 45 55 55 63 63 ……0 0 0 0 ……
1 1 4 4 10　　 10　　 20　　 20 ……

可以用s/2向下取整+1先把重复的删除（calc(n,s/2+1)）

然后这个矩阵就有有个规律了：

如果s/2+1小于11的话，memory[i][j]=memory[x-1][y]+memory[x][y-1]

否则memory[i][j]=memory[x-1][y]+memory[x][y-1]-1

#pragma GCC optimize(2)#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #define IL inlineusing namespace std;unsigned long long n,s,ans,sum;bool vis[100][1001];unsigned long long memory[100][1001]={{ 0},{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,},{ 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1,0,0},{}};IL unsigned long long calc(int x,int y){ if(x==1||x==0) { if(y<=20) return 1; else return 0; } if(y==1) return 1; if(vis[x][y]||memory[x][y]) return memory[x][y]; memory[x-1][y]=calc(x-1,y); memory[x][y-1]=calc(x,y-1); vis[x-1][y]=vis[x][y-1]=1; return memory[x][y]=memory[x-1][y]+memory[x][y-1]-(int)(y>=20);}IL int read(){ char ch;int x=0; ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; }int main(){// freopen("tickets.in","r",stdin);// freopen("tickets.out","w",stdout); n=read(); s=read(); ans=calc(n,s/2+1); cout<