01bfs　tsp bit,累積dp 周期性(ダブリ)

#include<iostream>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<functional>
#include<iterator>
#include<complex>
#include<fstream>
#include<random>
#include<ctype.h>
#include<stdio.h>
#include<unordered_map>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using PII = pair<ll, ll>;
using piii = pair<pii, pii>;
using Pi = pair<int, pii>;
using Graph = vector<vector<int>>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
bool check(int x, int y) {
    if (0 <= x && x<55 && 0 <= y && y<55)return true;
    else return false;
}
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
    if (x < y)swap(x, y);
    if (y == 0)return x;
    return gcd(y, x%y);
}
void mul(ll a, ll b) {
    a = a * b % INF;
}
using Graph = vector<vector<int>>;

//iの逆元mod inf
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
const double PI = 3.14159265358979323846;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;//mod pにおける1,2,,,nの逆元
    for (int i = 2; i < MAX; ++i) {
        fac[i] = fac[i - 1] * i%INF;
        inv[i] = INF - inv[INF%i] * (INF / i) % INF;
        finv[i] = finv[i - 1] * inv[i] % INF;
    }
}

ll COM(int n, int k) {
    if (n < k)return 0;
    if (n < 0 || k < 0)return 0;
    return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
double Euclidean_distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//素因数分解
map<int, int>prime_factor(int n) {
    map<int, int>res;
    for (int i = 2; i*i <= n; ++i) {
        while (n%i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1)res[n] = 1;
    return res;
}


ll powmod(ll a, ll k, ll mod) {
    ll ap = a, ans = 1;
    while (k) {
        if (k & 1) {
            ans *= ap;
            ans %= mod;
        }
        ap = ap * ap;
        ap %= mod;
        k >>= 1;
    }
    return ans;
}
ll invi(ll a, ll mod) {
    return powmod(a, mod - 2, mod);
}
#define PI 3.14159265358979323846  // 円周率
//逆元Aを足したときのmodで割った余りは
//+=invi(A)
//Yで割ることはY^(10^9+7)-2を掛けることは同値
///////////////////////////////////////

//移動bを使った回数をコストとする
//まずスタート地点からbfsで新しくコスト0でたどり着けるマスを列挙する
//次にコスト0でたどり着けるマスから移動bでたどり着けまたコスト0以下でたどり着けないマスを列挙する
//これを繰り返し全ての到達可能なマスに対して到達するための必要コストを求められる
//dequeを使い01bfs
char s[1010][1010];
int d[1010][1010];
int main() {
    int h, w; cin >> h >> w;
    int ch, cw, dh, dw;
    cin >> ch >> cw;
    cin >> dh >> dw;
    ch--, cw--;
    dh--, dw--;
    REP(i, h) {
        REP(j, w) {
            cin >> s[i][j];
            d[i][j] = INF;
        }
    }
    d[ch][cw] = 0;
    deque<pii>q;
    q.push_back({ ch,cw });
    while (q.size()) {
        auto p = q.front();
        q.pop_front();
        int i = p.first, j = p.second;
        for (int k = 0; k < 4; ++k) {
            int i2 = i + dy[k], j2 = j + dx[k];
            if (i2 < 0 || i2 >= h || j2 < 0 || j2 >= w||s[i2][j2]=='#')continue;
            if (d[i2][j2] > d[i][j]) {
                d[i2][j2] = d[i][j];
                q.push_front({ i2,j2 });
            }
        }
        for (int k = -2; k <= 2; ++k) {
            for (int l = -2; l <= 2; ++l) {
                int i2 = i + k, j2 = j + l;
                if (i2 < 0 || i2 >= h || j2 < 0 || j2 >= w ||s[i2][j2]=='#')continue;
                if (d[i2][j2] > d[i][j] + 1) {
                    d[i2][j2] = d[i][j] + 1;
                    q.push_back({ i2,j2 });
                }
            }
        }
    }
    if (d[dh][dw] == INF)cout << -1 << endl;
    else cout << d[dh][dw] << endl;
    return 0;
}

int n; 
int dp[1 << 17][20];//dp[s][v]:sを通ってvにいるときの後に通る最短経路長
int x[20], y[20], z[20];
vector<pii>G[20];
int main() {
    cin >> n;
    REP(i, n) {
        cin >> x[i] >> y[i] >> z[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int tmp = abs(x[i] - x[j]) + abs(y[i] - y[j]);
            G[i].push_back({ j,tmp + max(0,z[j] - z[i]) });
            G[j].push_back({ i,tmp + max(0,z[i] - z[j]) });
        }
    }
    REP(i, (1 << 17)) {
        REP(j, 17) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (dp[i][j] == INF)continue;
            for (int k = 0; k < G[j].size(); ++k) {
                pii e = G[j][k];
                if (i&(1 << e.first))continue;
                dp[i | (1 << e.first)][e.first] = min(dp[i | (1 << e.first)][e.first], dp[i][j] + e.second);
            }
        }
    }
    cout << dp[(1 << n) - 1][0] << endl;
    return 0;
}

const int mo = 998244353;
//累積dp
//区間[L1,R1]から整数を選んだ時,d[i]:=d[i-L1]+d[i-L1-1]+.....+d[i-R1]
//d[i]:=Σ(1<=k<=K)Σ(Lk<=j<=Rk)d[i-j] 
//ここでΣd[i-j]はd[i]の累積和で高速に計算できるのでd[i]の累積和をc[i+1]とすると
//c[i+1]=d0+d1+......+diとなり
//d[i]=Σ(1<=k<=K)(c[i-Lk+1]-c[i-Rk])となる
//よってd[i]の値が確定した後にc[i+1]=c[i]+d[i]と更新する
int main() {
    int n, k; cin >> n >> k;
    int L[11], R[11];
    REP(i, k) {
        cin >> L[i] >> R[i];
    }
    vector<ll>dp(200010,0);
    vector<ll>dpsum(200010, 0);
    dp[0] = 1;
    dpsum[1] = 1;
    for (int i = 1; i <= n; ++i) {
        REP(j, k) {
            int l = max(i - R[j], 0);
            int r = max(i - L[j]+1, 0);
            dp[i] += (dpsum[r] - dpsum[l] + mo) % mo;
            dp[i] %= mo;
        }
        dpsum[i+1] = dp[i] + dpsum[i];
        dpsum[i + 1] %= mo;
    }
    cout << dp[n - 1] << endl;
    return 0;
}

//周期性に着目
//かつて来たことのある地点に再び来たらそこから先は同じサイクルを延々と未来永劫繰り返す
//最初は愚直にx,x^2,x^4,,,をmで割った余りを計算していく
//その過程でn項目までまで到達した場合はその時点での答えをリターンする
//a項目で初めてかつて来たことのある地点に到達した場合は次のようになる
//１、N-=aとする　２、サイクルの項数をcとしてq=N/c,r=N%cとすると
//サイクルはq周して追加でrステップ進む
int main() {
    ll N, X, M;
    cin >> N >> X >> M;
    vector<int>ord(M, -1);//かつて来た地点を求める
    vector<ll>rireki, syu;
    ll res = 0;
    for (int n = 0; n < N; ++n) {
        //かつて来た地点に戻ったら
        if (ord[X] != -1) {
            ll p = ord[X];
            for (ll i = p; i < n; ++i)syu.push_back(rireki[i]);
            break;
        }
        ord[X] = n;
        rireki.push_back(X);
        res += X;
        X = (X*X) % M;
    }
    N -= rireki.size();
    if (N == 0) {
        cout << res << endl;
        return 0;
    }
    vector<ll>syusum;
    syusum.push_back(0);
    for (int i = 0; i < syu.size(); ++i) {
        syusum.push_back(syusum[i] + syu[i]);
    }
    ll q = N / syu.size();
    ll r = N % syu.size();
    res += syusum[syu.size()] * q + syusum[r];
    cout << res << endl;
    return 0;
}