fork download
copy 
  1. //
  2. //  A.cpp
  3. //  CODE
  4. //
  5. //  Created by Vikas Yadav on 29/10/14.
  6. //  Copyright (c) 2014 Vikas Yadav. All rights reserved.
  7. //
  8.  
  9. #include <cstring>
  10. #include <vector>
  11. #include <list>
  12. #include <map>
  13. #include <set>
  14. #include <deque>
  15. #include <queue>
  16. #include <stack>
  17. #include <bitset>
  18. #include <algorithm>
  19. #include <functional>
  20. #include <numeric>
  21. #include <utility>
  22. #include <sstream>
  23. #include <iostream>
  24. #include <iomanip>
  25. #include <cstdio>
  26. #include <cmath>
  27. #include <cstdlib>
  28. #include <ctime>
  29. #include <fstream>
  30. #include <iterator>
  31. #include <memory.h>
  32. #include <cassert>
  33.  
  34. using namespace std;
  35.  
  36. #define assn(n, a, b) assert(n<=b and n>=a)
  37. #define pb push_back
  38. #define mp make_pair
  39. #define gc getchar_unlocked
  40. #define F first
  41. #define S second
  42. #define endl '\n'
  43.  
  44. #define MOD 1000000007
  45. #define N 112
  46. #define M 112
  47. #define K 11
  48.  
  49. int n,k,m;
  50. long long dp[N][M][K+2];
  51. int states[(1<<K)][K+2][2];
  52.  
  53. bool charat(int str,int ind){
  54.     return ((str&(1<<ind))>>ind);
  55. }
  56.  
  57. int getNextState(int str,int state, int x){
  58.     if (state<k)
  59.         if(x==charat(str,state))
  60.             return state+1;
  61.     int ns, i;
  62.     for (ns = state; ns > 0; ns--)
  63.         if(charat(str,ns-1) == x){
  64.             for(i = 0; i < ns-1; i++)
  65.                 if (charat(str,i)!=charat(str,state-ns+1+i))
  66.                     break;
  67.             if (i == ns-1)
  68.                 return ns;
  69.         }
  70.     return 0;
  71. }
  72.  
  73. void build_states(int str){
  74.     states[str][0][0] = 0,states[str][0][1] = 0;
  75.     states[str][0][(str&1)] = 1;
  76.     for(int a=0;a<=k;a++)
  77.         for(int b=0;b<2;b++)
  78.             states[str][a][b] = getNextState(str, a, b);
  79. }
  80.  
  81. void func(){
  82.     long long ans = 0;
  83.     for(int str=0;str<(1<<k);str++){
  84.         for(int a=0;a<=n;a++)
  85.             for(int b=0;b<=n;b++)
  86.                 for(int c=0;c<=k;c++)
  87.                     dp[a][b][c] = 0;
  88.         dp[k][0][0] = 1;
  89.         for(int a=k;a<=n;a++){
  90.             for(int b=0;b<=a;b++){
  91.                 for(int c=0;c<=k;c++){
  92.                     dp[a+1][b+(states[str][c][0]==k?1:0)][states[str][c][0]] += (dp[a][b][c]);
  93.                     dp[a+1][b+(states[str][c][1]==k?1:0)][states[str][c][1]] += (dp[a][b][c]);
  94.                     while(dp[a+1][b+(states[str][c][0]==k?1:0)][states[str][c][0]]>=MOD)
  95.                         dp[a+1][b+(states[str][c][0]==k?1:0)][states[str][c][0]] -= MOD;
  96.                     while(dp[a+1][b+(states[str][c][1]==k?1:0)][states[str][c][1]]>=MOD)
  97.                         dp[a+1][b+(states[str][c][1]==k?1:0)][states[str][c][1]] -= MOD;
  98.                 }
  99.             }
  100.         }
  101.         for(int b=m+1;b<=n;b++)
  102.             for(int c=0;c<=k;c++){
  103.                 ans += dp[n][b][c];
  104.                 while(ans>=MOD)
  105.                     ans -= MOD;
  106.             }
  107.     }
  108.     printf("%lld\n", ans);
  109. }
  110.  
  111. int main(){
  112.     int tt = 1;
  113.     //double st = clock();
  114.     //freopen("./Input/in11.in", "r", stdin);
  115.     //freopen("./Output/out111.out", "w", stdout);
  116.     scanf("%d", &tt);
  117.     assn(tt, 1, 10);
  118.     while(tt--){
  119.         scanf("%d%d%d", &n, &k, &m);
  120.         assn(n, 1, 100);
  121.         assn(k, 0, min(10, n));
  122.         assn(m, 0, n-1);
  123.         for(int a=0;a<(1<<K);a++)
  124.             for(int b=0;b<K+2;b++)
  125.                 states[a][b][0] = 0,states[a][b][1] = 0;
  126.         for(int a=0;a<(1<<k);a++)build_states(a);
  127.         func();
  128.     }
  129.     return 0;
  130. }
  131.  
Runtime error #stdin #stdout #stderr 0s 4900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:120: int main(): Assertion `n<=100 and n>=1' failed.
https://ideone.com/l3h5ru
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!