UVA 12063 Zeros and ones 一道需要好好体会的好题

雨点打透心脏的1/2处 2021-09-29 23:42 162阅读 0赞

![70][]

![70 1][]

#include<bits/stdc++.h>
    #include<stdio.h>
    #include<iostream>
    #include<cmath>
    #include<math.h>
    #include<queue>
    #include<set>
    #include<map>
    #include<iomanip>
    #include<algorithm>
    #include<stack>
    #define inf 0x3f3f3f3f
    using namespace std;
    typedef unsigned long long ll;
    ll dp[35][35][105];
    int n,k;
    
    /*
    ll dfs(int z,int o,int m) {
        if(z<0 || o<0) return 0;
        ll &ans=dp[z][o][m];
        if(ans>=0) return ans;
        ans=0;
        ans=dfs(z-1,o,m*inv[2])+dfs(o-1,z,((m+k-1)%k*inv[2])%k);
        return ans;
    }*/
    
    void solve() {
        for(int i=0;i<=33;i++) {
            for(int j=0;j<=33;j++) {
                for(int m=0;m<k;m++) {
                    dp[i+1][j][(2*m)%k]+=dp[i][j][m];
                    dp[i][j+1][(2*m+1)%k]+=dp[i][j][m];
                    //cout<<dp[n/2][n/2-1][0]<<endl;
                }
            }
        }
    }
    ll  C[65][65];
    ll solve2() {
        return C[n-1][n/2];
    }
    
    int id=1;
    int main()
    {
    #ifndef ONLINE_JUDGE
       freopen("in.txt","r",stdin);
    #endif // ONLIN
        int t;
        cin>>t;
    
        for(int i=0;i<=64;i++)C[i][0]=1;
        for(int i=1;i<=64;i++)
            for(int j=0;j<=i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    
    
    
        while(t--)
        {
            memset(dp,0,sizeof(dp));
            cin>>n>>k;
            if(k==1)dp[0][0][0]=1;
            else
            dp[0][0][1]=1;
            ll ans;
            if( (n&1) || k==0) ans=0;
            else solve(),ans=dp[n/2][n/2-1][0];
            cout<<"Case "<<id++<<": "<<ans<<endl;
        }
    }

转载于:https://www.cnblogs.com/linruier/p/9556907.html

[70]: /images/20210725/5cef2c92c9f347bfb9034a3b737e830b.png
[70 1]: /images/20210725/91a0675eb3a449569e269b830808b2a7.png