API tools faq
paste
welleyth

641. C FULL

welleyth
May 27th, 2022 (edited)
139
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.54 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. //#define int long long
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. #pragma GCC optimize("Ofast")
  12. #pragma GCC optimize("unroll-loops")
  13.  
  14. constexpr int INF = (int)1e9;
  15. constexpr int N = (int)5e5 + 111;
  16. constexpr int md = (int)1e9+7;
  17. constexpr int mdPower = (int)1e9+7 - 1;
  18.  
  19. int mex(vector<int> v){
  20.     if(v.empty())
  21.         return 0;
  22.     set<int> st(v.begin(),v.end());
  23.     v = vector<int>(st.begin(),st.end());
  24.     for(int i = 0; i < v.size(); i++)
  25.         if(i != v[i])
  26.             return i;
  27.     return v.size();
  28. }
  29.  
  30. int mex(set<int>& st){
  31.     int c = 0;
  32.     for(auto& x : st){
  33.         if(x != c)
  34.             return c;
  35.         c++;
  36.     }
  37.     return st.size();
  38. }
  39.  
  40. int CC[10];
  41.  
  42. int mex(){
  43.     int c = 0;
  44.     for(int i = 0; i < 10; i++){
  45.         if(CC[i] == 0)
  46.             return i;
  47.     }
  48.     assert(false);
  49.     return -1;
  50. }
  51.  
  52. map<vector<int>,int> grundy;
  53. vector<int> PossibleMoves;
  54.  
  55. int get(vector<int>& g){
  56.     if(grundy.count(g))
  57.         return grundy[g];
  58.     vector<int> goGrundy;
  59.  
  60.     int sz = g.size();
  61.     for(auto& x : PossibleMoves){
  62.         if((int)g.size() - x <= 0 || g[sz-x-1] != 1)
  63.             continue;
  64.         vector<int> to = g;
  65.         for(int j = 0; j < x; j++)
  66.             to.pop_back();
  67.         assert(to != g);
  68.         goGrundy.pb(get(to));
  69.     }
  70. //    for(auto& x : goGrundy)
  71. //        cerr << x << " ";
  72. //    cerr << "\n";
  73.     return grundy[g] = mex(goGrundy);
  74. }
  75.  
  76. struct basis{
  77.     vector<int> b;
  78.     basis(){}
  79.     void add(int x){
  80.         for(auto& y : b)
  81.             x = min(x,x^y);
  82.         if(x != 0)
  83.             b.pb(x);
  84.     }
  85.     bool check(int x){
  86.         for(auto& y : b)
  87.             x = min(x,y^x);
  88.         return x == 0;
  89.     }
  90. };
  91.  
  92. int cnt[1<<6][101][10];
  93.  
  94. int bpow(int a,int b){
  95.     if(b == 0)
  96.         return 1;
  97.     if(b % 2 == 0){
  98.         int t = bpow(a,b>>1);
  99.         return 1ll*(t*t)%md;
  100.     }
  101.     return 1ll*a*bpow(a,b-1)%md;
  102. }
  103.  
  104. int dp[2][9][9][9][9][9][9]; /// dp[pos][g1][g2][g3][g4][g5][g6]
  105. /// if g_i == INF then there is a zero at that position
  106. /// INF = 9
  107.  
  108. void add(int& a,int b){
  109.     a += b; if(a >= md) a-=md;
  110. }
  111. void add(long long& a,long long b){
  112.     a += b; if(a >= md) a-=md;
  113. }
  114.  
  115. int MEX = 0;
  116.  
  117. void ADD(int x){
  118.     CC[x]++;
  119.     while(CC[MEX])
  120.         MEX++;
  121.     return;
  122. }
  123.  
  124. void DEL(int x){
  125.     CC[x]--;
  126.     if(CC[x] == 0 && x < MEX)
  127.         MEX = x;
  128.     return;
  129. }
  130.  
  131. typedef long long ll;
  132.  
  133. vector<ll> operator *(vector<ll> a,vector<ll> b){
  134.     vector<ll> c(8,0);
  135.     for(int i = 0; i < 8; i++){
  136.         for(int j = 0; j < 8; j++){
  137.             add(c[i^j],1ll*a[i]*b[j]%md);
  138.         }
  139.     }
  140.     return c;
  141. }
  142.  
  143. vector<ll> NULL_MATRICE = {1,0,0,0,0,0,0,0};
  144.  
  145. vector<ll> bpow(vector<ll>& a,ll b){
  146.     if(b == 0)
  147.         return NULL_MATRICE;
  148.     if(b == 1)
  149.         return a;
  150.     if(b % 2 == 0){
  151.         vector<ll> t = bpow(a,b>>1);
  152.         return t*t;
  153.     }
  154.     return a * bpow(a,b-1);
  155. }
  156.  
  157. void solve(){
  158. //    for(int i = 0; i < 8; i++){
  159. //        for(int j = 0; j < 8; j++){
  160. //            cerr << i << " " << j << "\n";
  161. //            for(int t = 0; t < 8; t++){
  162. //                cerr << "(" << i << "," << t << ")*(" << t << "," << j << ")\n";
  163. //            }
  164. //        }
  165. //    }
  166. //
  167. //    return;
  168.     int n;
  169.     cin >> n;
  170.  
  171.     vector<pair<ll,int>> In;
  172.     set<int> st;
  173.     int C = 0;
  174.     int mx = 0;
  175.     for(int i = 0; i < n; i++){
  176.         ll a,b;
  177.         cin >> a >> b;
  178.         In.pb(mp(a,b));
  179.         st.insert(b);
  180.         C += (b-1)*a;
  181.         C %= mdPower;
  182.         mx = max(mx,C);
  183.     }
  184.     int k;
  185.     cin >> k;
  186.     int PossibleMASK = 0;
  187.     bool have[7] = {};
  188.     for(int i = 0; i < k; i++){
  189.         int a;
  190.         cin >> a;
  191.         PossibleMoves.pb(a);
  192.         have[a] = 1;
  193.         a--;
  194.         PossibleMASK |= (1 << a);
  195.     }
  196.  
  197.     for(int m1 = PossibleMASK; m1 < PossibleMASK+1; m1++){
  198.         PossibleMoves.clear();
  199.         for(int i = 0; i < 6; i++){
  200.             if(m1 >> i & 1){
  201.                 PossibleMoves.pb(i+1);
  202.             }
  203.         }
  204.         memset(dp,0,sizeof dp);
  205.         dp[0][8][8][8][8][8][8] = 1;
  206.         #pragma GCC ivdep
  207.         for(int i = 1; i <= 100; i++){
  208.             int g[6];
  209.             #pragma GCC ivdep
  210.             for(g[0] = 0; g[0] < 9; g[0]++){
  211.                 if(have[6])
  212.                     ADD(g[0]);
  213.                 #pragma GCC ivdep
  214.                 for(g[1] = 0; g[1] < 9; g[1]++){
  215.                     if(have[5])
  216.                         ADD(g[1]);
  217.                     #pragma GCC ivdep
  218.                     for(g[2] = 0; g[2] < 9; g[2]++){
  219.                         if(have[4])
  220.                             ADD(g[2]);
  221.                         #pragma GCC ivdep
  222.                         for(g[3] = 0; g[3] < 9; g[3]++){
  223.                             if(have[3])
  224.                                 ADD(g[3]);
  225.                             #pragma GCC ivdep
  226.                             for(g[4] = 0; g[4] < 9; g[4]++){
  227.                                 if(have[2])
  228.                                     ADD(g[4]);
  229.                                 #pragma GCC ivdep
  230.                                 for(g[5] = 0; g[5] < 9; g[5]++){
  231.                                     /// HERE SHOULD BE NOT THIS
  232.                                     /// ADD ONLY POS WE CAN COME FROM
  233. //                                    gg.clear();
  234. //                                    for(auto& x : PossibleMoves) gg.push_back(g[6-x]);
  235.                                     if(have[1])
  236.                                         ADD(g[5]);
  237.                                     int m = MEX;
  238.                                     add(cnt[m1][i][m],dp[0][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]]);
  239.                                     add(dp[1][g[1]][g[2]][g[3]][g[4]][g[5]][m],
  240.                                         dp[0][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]]);
  241.                                     add(dp[1][g[1]][g[2]][g[3]][g[4]][g[5]][8],
  242.                                         dp[0][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]]);
  243.                                     if(have[1])
  244.                                         DEL(g[5]);
  245.                                 }
  246.                                 if(have[2])
  247.                                     DEL(g[4]);
  248.                             }
  249.                             if(have[3])
  250.                                 DEL(g[3]);
  251.                         }
  252.                         if(have[4])
  253.                             DEL(g[2]);
  254.                     }
  255.                     if(have[5])
  256.                         DEL(g[1]);
  257.                 }
  258.                 if(have[6])
  259.                     DEL(g[0]);
  260.             }
  261.             for(g[0] = 0; g[0] < 9; g[0]++){
  262.                 for(g[1] = 0; g[1] < 9; g[1]++){
  263.                     for(g[2] = 0; g[2] < 9; g[2]++){
  264.                         for(g[3] = 0; g[3] < 9; g[3]++){
  265.                             for(g[4] = 0; g[4] < 9; g[4]++){
  266.                                 for(g[5] = 0; g[5] < 9; g[5]++){
  267.                                     dp[0][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]] = dp[1][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]];
  268.                                     dp[1][g[0]][g[1]][g[2]][g[3]][g[4]][g[5]] = 0;
  269.                                 }
  270.                             }
  271.                         }
  272.                     }
  273.                 }
  274.             }
  275. //            cerr << i << "\n";
  276. //            cout << "cnt[" << m1 << "][" << i << "] = {";
  277. //            for(int j = 0; j < 8; j++){
  278. //                cout << cnt[m1][i][j];
  279. //                if(j != 7)
  280. //                    cout << ",";
  281. //            }
  282. //            cout << "};\n";
  283.         }
  284.     }
  285. //    return;
  286.  
  287.     vector<ll> A(8,0);
  288.     A[0] = 1;
  289.     for(auto&[x,y] : In){
  290.         vector<ll> B(8,0);
  291.         for(int i = 0; i < 8; i++){
  292.             B[i] = cnt[PossibleMASK][y][i];
  293.         }
  294. //        cerr << "B:\n";
  295. //        for(auto& X : B){
  296. //            cerr << X << " ";
  297. //        }
  298. //        cerr << "\n";
  299. //        cerr << "A:\n";
  300. //        for(auto& X : A){
  301. //            cerr << X << " ";
  302. //        }
  303. //        cerr << "\n";
  304.         A = A * bpow(B,x);
  305.     }
  306.  
  307.     cout << (1ll * A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7]) % md << "\n";
  308.  
  309.     return;
  310. }
  311.  
  312. signed main(){
  313.     ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  314. //    freopen("input.txt","r",stdin);
  315. //    freopen("output.txt","w",stdout);
  316.     int tests = 1;
  317. //    cin >> tests;
  318.     for(int test = 1; test <= tests; test++){
  319.         solve();
  320.     }
  321.     return 0;
  322. }
  323. /**
  324. Possible: 1 2 3
  325. 1 0 0 0 0 0 0 0
  326. 1 1 0 0 0 0 0 0
  327. 1 2 1 0 0 0 0 0
  328. 1 3 3 1 0 0 0 0
  329. 9 3 3 1 0 0 0 0
  330. 17 8 5 2 0 0 0 0
  331. 25 24 11 4 0 0 0 0
  332.  
  333.  
  334. cnt[n][g][mask] - количество последовательностей длины n, которые имеют число гранди g и последние k чисел в ней - mask
  335.  
  336. cnt[n][mex][mask]
  337.  
  338. 6^6
  339.  
  340. dp[n][mex][mask]
  341.  
  342.  
  343. for(int i = 0; i < n; i++){
  344.     for(int mask = 0; mask < (1 << 6); mask++){
  345.  
  346.     }
  347. }
  348.  
  349. b -> a -> cur
  350. b -> cur
  351.  
  352. cnt[pos][g1][g2][g3][g4][g5][g6]
  353.  
  354. for(int i = 0; i < n; i++){
  355.     for(int j = 0; j < n; j++){
  356.         for(int t = 0; t < n; t++){
  357.             add(g[i][j],a[i][t]*b[t][j])
  358.  
  359.  
  360.  
  361. cnt[1]
  362. cnt[2]
  363. cnt[3]
  364. cnt[4]
  365. cnt[5]
  366. cnt[6]
  367.  
  368. 0 0
  369. A(0,0)*B(0,0)
  370. A(0,1)*B(1,0)
  371. A(0,2)*B(2,0)
  372. A(0,3)*B(3,0)
  373. A(0,4)*B(4,0)
  374. A(0,5)*B(5,0)
  375. A(0,6)*B(6,0)
  376. A(0,7)*B(7,0)
  377.  
  378. 0 1
  379. A(0,0)*B(0,1)
  380. A(0,1)*B(1,1)
  381. A(0,2)*B(2,1)
  382. A(0,3)*B(3,1)
  383. A(0,4)*B(4,1)
  384. A(0,5)*B(5,1)
  385. A(0,6)*B(6,1)
  386. A(0,7)*B(7,1)
  387.  
  388. **/
  389.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!