P1357-花园

忘是亡心i 2023-06-01 08:54 14阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 typedef double db;
     5 #define INF 0x3f3f3f3f
     6 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     7 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     8 
     9 inline ll read()
    10 {
    11     ll ans = 0;
    12     char ch = getchar(), last = ' ';
    13     while(!isdigit(ch)) last = ch, ch = getchar();
    14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    15     if(last == '-') ans = -ans;
    16     return ans;
    17 }
    18 inline void write(ll x)
    19 {
    20     if(x < 0) x = -x, putchar('-');
    21     if(x >= 10) write(x / 10);
    22     putchar(x % 10 + '0');
    23 }
    24 ll N,M,K;
    25 ll cnt,ans;
    26 ll dp[1<<5],a[1<<5][1<<5];
    27 bool pd[1<<5];
    28 void mul1(ll a[1<<5][1<<5])
    29 {
    30     ll c[1<<5][1<<5];
    31     memset(c,0,sizeof(c));
    32     _for(i,0,1<<5)
    33         _for(j,0,1<<5)
    34             _for(k,0,1<<5)
    35                 c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % 1000000007;
    36     memmove(a,c,sizeof(c));
    37 }
    38 void mul2(ll dp[1<<5], ll a[1<<5][1<<5])
    39 {
    40     ll c[1<<5];
    41     memset(c,0,sizeof(c));
    42     _for(j,0,1<<5)
    43         _for(k,0,1<<5)
    44             c[j] = (c[j] + dp[k] * a[k][j]) % 1000000007;
    45     memmove(dp,c,sizeof(c));
    46 }
    47 int main()
    48 {
    49     N = read(), M = read(), K = read();
    50     _for(i,0,1<<M)
    51     {
    52         cnt = 0;
    53         _for(j,0,M+1)
    54         if(i & (1 << j))
    55             cnt ++;
    56         if(cnt <= K)
    57             pd[i] = true;
    58     }
    59 
    60     _for(i,0,1<<M)
    61     {
    62         if(pd[i])
    63         {
    64             memset(dp,0,sizeof(dp));
    65             memset(a,0,sizeof(a));
    66             dp[i] = 1;
    67             _for(j,0,1<<M)
    68             if(pd[j])
    69             {
    70                 a[j>>1][j] = 1;
    71                 a[(j>>1)+(1<<(M-1))][j] = 1;
    72             }
    73             for(ll y = N; y ; y >>= 1,mul1(a))
    74                 if(y & 0x1)
    75                     mul2(dp,a);
    76             ans = (ans+dp[i])%1000000007;
    77         }
    78     }
    79     write(ans);
    80     return 0;
    81 }

转载于:https://www.cnblogs.com/Asurudo/p/11473689.html