DAY12 矩阵快速幂、质数与约数

没有开头的开头

快速幂:快速幂多于求解a的b次方这样的问题,通常使用分治求解。

递归:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int quick_pow(int a,int b,int n)
{
    if(b==1)return a;
    if(b%2==0)
    {
        int t=quick_pow(a,b/2,n);
        return t*t%n;
    }
    else
    {
        int t=quick_pow(a,b/2,n);
        t=t*t%n;
        t=t*a%n;
        return t;
    }
}

非递归:


1
2
3
4
5
6
7
8
9
10
11
int quick_pow(int a,int b,int n)
{
    int res=1;
    while(b)
    {
        if(b%2==1)res=res*a%n;
        a=a*a%n;
        b>>=1;
    }
    return res;
}

单位矩阵:

主对角线元素都为1,其余元素全为0的矩阵称n阶单位矩阵。

在矩阵乘法中,单位矩阵的任意次方都为它自己。

矩阵加减:相应的位置相加减。

矩阵乘法:

例题:斐波那契数列

两种方法:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
// F[2n] = F[n+1]2 - F[n-1]2 = (2F[n-1] + F[n]) · F[n] ①
// F[2n+1] = F[n+1]2 + F[n]2 ②
typedef long long LL;
typedef pair<LL, LL> PII;
const LL mod = 1e9 + 7;
LL n;
unordered_map<LL, LL> m;
LL f(LL i) {
    LL res1, res2, res;
    if (i < 3)
        return 1LL;
    auto it = m.find(i);
    if (it == m.end()) {
        if (i & 1) {
            res1 = f(i >> 1);
            res2 = f(i + 1 >> 1);
            res = (res1 * res1 + res2 * res2) % mod;
        } else {
            res1 = f(i - 2 >> 1);
            res2 = f(i >> 1);
            res = ((res1 << 1) + res2) * res2 % mod;
        }
        m.insert(PII(i, res));
        return res;
    } else
        return it->second;
}
int main() {
    scanf("%lld", &n);
    printf("%lld", f(n));
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
struct Matrix {
    long long a[3][3];
    Matrix() { memset(a, 0, sizeof a); }
    Matrix operator*(const Matrix &b) const {
        Matrix res;
        for (long long i = 1; i <= 2; ++i) {
            for (long long j = 1; j <= 2; ++j) {
                for (long long k = 1; k <= 2; ++k) res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
            }
        }
        return res;
    }
} ans, B;
void init() {
    B.a[1][1] = B.a[1][2] = B.a[2][1] = 1;
    ans.a[1][1] = ans.a[1][2] = 1;
}
void qpow(long long b) {
    while (b) {
        if (b & 1)
            ans = ans * B;
        B = B * B;
        b >>= 1;
    }
}
int main() {
    long long n;
    scanf("%lld", &n);
    if (n <= 2) {
        printf("1");
        return 0;
    }
    init();
    qpow(n - 2);
    printf("%lld", ans.a[1][1] % mod);
    return 0;
}

(第一种为公式优化,第二种为矩阵快速幂)

质数与约数:

例题:质数距离

代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 10000005;
ll l, r, f[N], st[N], primes[N], cnt = 0, x, y, x2, y2;
inline void get_primes() {
    for (int i = 2; i <= N; i++) {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= N / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
int main() {
    ll a, b;
    get_primes();
    while (scanf("%lld%lld", &l, &r) != EOF) {
        if (l == 1)
            l = 2;
        memset(f, 0, sizeof(f));
        for (ll i = 0; i < cnt; i++) {
            a = (l - 1) / primes[i] + 1;
            b = r / primes[i];
            for (ll j = a; j <= b; j++) {
                if (j > 1)
                    f[j * primes[i] - l] = 1;
            }
        }
        ll p = -1, Max = -1, Min = 0x3f3f3f3f;
        for (ll i = 0; i <= r - l; i++) {
            if (!f[i]) {
                if (p == -1) {
                    p = i;
                    continue;
                }
                if (Max < i - p) {
                    Max = i - p;
                    x = p + l;
                    y = i + l;
                }
                if (Min > i - p) {
                    Min = i - p;
                    x2 = p + l;
                    y2 = i + l;
                }
                p = i;
            }
        }
        if (Max == -1)
            printf("There are no adjacent primes.\n");
        else
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n", x2, y2, x, y);
    }
    return 0;
}

2021.7.22

明天就要走啦!

今天学习了单调队列,

滑动窗口


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int head=1, tail=1, head1=1, tail1=1;
int q[1000001], qq[1000001], a[1000001];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    q[1] = 1;
    for (int i=1; i<=n; i++)
    {
        if (head<=tail && q[head] < i-k+1)  head++;
        while (head<=tail && a[i] <= a[q[tail]]) tail--;
        q[++tail] = i;
        if (i>k-1) cout << a[q[head]] <<' ';
    }
    cout << endl;
    qq[1] = 1;
    for (int i=1; i<=n; i++)
    {
        if (head1<=tail1 && qq[head1] < i-k+1)  head1++;
        while (head1<=tail1 && a[i] >= a[qq[tail1]]) tail1--;
        qq[++tail1] = i;
        if (i>k-1) cout << a[qq[head1]] <<' ';
    }
    return 0;
}

[USACO19DEC]Milk Visits S


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
int fa[1000001];
int check (int x)
{
    if (fa[x] == x) return x;
    return fa[x] = check (fa[x]);
}
int heb (int x, int y)
{
    return fa[check (x)] = check(y);
}
int main()
{
    char a[1000001];
    int n, m, x, y;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        fa[i] = i;
        cin >> a[i];
    }
    for (int i=1; i<=n-1; i++)
    {
        cin >> x >> y;
        if (a[x] == a[y]) heb (x, y);
    }
    char c;
    int kk[1000001];
    for (int i=1; i<=m; i++)
    {
        cin >> x >> y >> c;
        if (check (x) != check (y) || a[x] == c)    kk[i] = 1;
        else kk[i] = 0;
    }
    for (int i=1; i<=m; i++)
    {
        cout << kk[i];
    }
    return 0;
}

 

长乐7.22集训

明天就要回家啦!想想就开心!    

 

1.线性筛素数:http://172.17.55.160/contest/179/problem/1

题解:线筛,多开一个数组存储第几个素数,用scanf快了1000ms。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h> //O(n) //用 最小 的质因数筛掉合数
using namespace std;

const int MAXN=100000005;
int cnt=0;
int prime[MAXN];
bool st[MAXN];
int f[MAXN];
int tail=1;

void init()
{
    for(int i=2;i<MAXN;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
            f[tail++]=i;
        }
        for(int j=0;prime[j]<MAXN/i;j++)
        {
            if(i*prime[j]>MAXN) break;
            st[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
   
}

int main()
{
    init();
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)
    {
        int a;
        scanf("%d",&a);
        printf("%d\n",f[a]);
    }
   
    return 0;
}

 

3.序列的第k个数:http://172.17.55.160/contest/178/problem/1

题解:快速幂:https://www.bilibili.com/video/BV1K441167eE?t=886


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=200907;
const ll N=1e9;
int t;
ll a,b,c,d,k,res;
ll mypow(ll x,ll y)
{
    ll sum=1LL;
    while(y)
    {
        if(y&1LL) sum=(sum*x)%MOD;
        y>>=1LL;
        x=x*x%MOD;
    }
    return sum;
}
void Judge()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
    if(b-a==c-b)
    {
        d=(b-a)%MOD;
        res=(a+(k-1)%MOD*d)%MOD;
    }
    else
    {
        d=(b/a)%MOD;
        res=a%MOD*mypow(d,k-1)%MOD;
    }
    printf("%lld\n",res);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        Judge();
    }

    return 0;
}

 

3.区间查改:http://172.17.55.160/contest/162/problem/2

题解:线段树,懒标记,pushdown


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

const int N=10000005;

int n,m;
int a[N];
struct node
{
    int l,r;
    long long sum,add;
}tr[N*4];

void pushup(int u)
{
    tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}

void pushdown(int u)
{
    node &root=tr[u],&left=tr[u*2],&right=tr[u*2+1];
    if(root.add)
    {
        left.add+=root.add,left.sum+=(long long)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(long long)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[r],0};
    else
    {
        tr[u]={l,r};
        int mid=(l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l && tr[u].r<=r)
    {
        tr[u].sum+=(long long)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else
    {
        pushdown(u);
        int mid=(tr[u].l+tr[u].r)/2;
        if(l<=mid) modify(u*2,l,r,d);
        if(r>mid) modify(u*2+1,l,r,d);
        pushup(u);
    }
}

long long query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
   
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    long long sum=0;
    if(l<=mid) sum=query(u*2,l,r);
    if(r>mid) sum+=query(u*2+1,l,r);
    return sum;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
   
    while(m--)
    {
        int c;
        int l,r,d;
        cin>>c;
        if(c==1)
        {
            cin>>l>>r>>d;
            modify(1,l,r,d);
        }
        else
        {
            cin>>l>>r;
            cout<<query(1,l,r)<<endl;
        }
    }

    return 0;
}

 

4.超级玛丽:洛谷P1000 (两年了,这题终于改出来了,无语子

题解:之前可能不小心多复制了一行,删了就过了。。

 

The end.

长乐一中半月欢乐游Day12

根据课程介绍,今天是数学基础的第一天。

最后一天的博客了

 

 

矩阵快速幂

快速幂是基础,这个这一用来降低递推递归的时间复杂度。

【例题1】序列的第k个数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 200907;
ll n,t;
ll a,b,c;
ll ans;
ll ksm(ll x,ll y)
{
    if(y == 1)return x;
    ll t = ksm(x,y/2);
    if(y%2==0)
        return t*t%MOD;
    else
        return x*t*t%MOD;
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>a>>b>>c>>n;
        if(a+c==b*2)
            printf("%lld\n",(a+(n-1)*(b-a))%MOD);
        else
        {
            ans=b/a%MOD;
            printf("%lld\n",a*ksm(ans,n-1)%MOD);
        }
    }
    return 0;
}

 

质数和约数

这个就相对好理解一点了

质数,以及约数。

【例题 1】线性筛素数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,q,k;
bool ss[100010006];
int prime[60000003],u;
void pprime()
{
    ss[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(!ss[i])
            prime[++u] = i;
        for(int j=1;j<=u&&i*prime[j]<=n;j++)
        {
            ss[i*prime[j]] = 1;
            if(i%prime[j]==0)break;
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&q);
    pprime();
    while(q--)
    {
        scanf("%d",&k);
        printf("%d\n",prime[k]);
    }
    return 0;
}

 

DAY11 状压DP与单调队列

今天讲状压DP和单调队列。

状压DP:

状压DP是一种借助状态压缩的DP,一般这样的DP状态很简单,一个状态由若干的数构成,每个数的取值是0或1,我们就可以把这若干个数压缩成一个二进制数。同时优化空间复杂度与时间复杂度。

查询第i位上是否为1:x&(1<<(i-1))!=0

把第i位上的数修改成0:x=x|(1<<(i-1))

把第i位上的数修改成1:x=x&~(1<<(i-1))

例题:Hamilton最短路径,在ybtoj上称最短路径:

code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 20;
int n;
int f[M][N];
int weight[N][N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%d", &weight[i][j]);
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1)
                for (int k = 0; k < n; k++)
                    if (i - (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
    printf("%d", f[(1 << n) - 1][n - 1]);
    return 0;
}

单调队列:

单调队列,即一个满足内部单调递增or递减的数据结构。其单调性所以经常被用来维护区间最值or降低DP的维数。

例题:滑动窗口

code:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000010;
int n, k;
int a[N], q[N];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1)
            hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    printf("\n");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1)
            hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    return 0;
}

博客不知道为什么最近时好时坏的,就只能先趁网好的时候发出去了。

长乐7.21集训

还是不知道写什么开头。

 

1.滑动窗口:http://172.17.55.160/contest/174/problem/1

题解:单调队列:https://www.bilibili.com/video/BV1rb411S7eB?t=503


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k;
int le=0,ri=0;
int a[N];
int q[N];
int id[N];
int a2[N];
int q2[N];
int id2[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(le<=ri && a[i]<q[ri]) ri--;
        ri++;
        q[ri]=a[i];
        id[ri]=i;
        if(id[le]+k<=i) le++;
        if(i>=k) cout<<q[le]<<" ";
    }
    cout<<endl;
    le=0,ri=0;
    for(int i=1;i<=n;i++)
    {
        while(le<=ri && a[i]>q2[ri]) ri--;
        ri++;
        q2[ri]=a[i];
        id2[ri]=i;
        if(id2[le]+k<=i) le++;
        if(i>=k) cout<<q2[le]<<" ";
    }

    return 0;
}

 

2.石子合并:https://www.acwing.com/activity/content/problem/content/1007/1/

题解:区间dp

模板:


1
2
3
for(int len=1;len<=n;len++)
    for(int l=1;l+len-1<=n;l++)
        int r=l+len-1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n;
int s[N*2];
int f[N*2][N*2];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            f[i][j]=1e8;
            for(int k=i;k<j;k++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n];

    return 0;
}

 

3.环形石子合并:https://www.acwing.com/activity/content/problem/content/1297/1/

题解:将n个节点的环变成n*2个节点线


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n;
int a[N*2];
int s[N*2];
int f[N*2][N*2];
int g[N*2][N*2];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=n*2;i++)
    {
        s[i]=s[i-1]+a[i];
    }
    memset(f,0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(f));
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n*2;i++)
        {
            int j=i+len-1;
            if(len==1) f[i][j]=g[i][j]=0;
            else
            {
                for(int k=i;k<j;k++)
                {
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                    g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
                }
            }
           
        }
    }
    int minv=1e8,maxv=-1e8;
    for(int i=1;i<=n;i++)
    {
        minv=min(minv,f[i][i+n-1]);
        maxv=max(maxv,g[i][i+n-1]);
    }
    cout<<minv<<endl<<maxv;

    return 0;
}

 

4.最短Hamilton路径:https://www.acwing.com/problem/content/93/

题解:状压dp,把矩阵中一整行当做一个状态表示值,因为原题中只有0和1,所以可以把每一行看做一个二进制的树,以此最为表示值,并计算。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int n;
int w[N][N];
int f[M][N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>w[i][j];
        }
    }
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=0;i<1<<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i>>j&1)
            {
                for(int k=0;k<n;k++)
                {
                    if((i-(1<<j))>>k&1)
                    {
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1];

    return 0;
}

 

The end.

2021.7.21

今天学习了...状压  dp,嗯...... 貌似是会了,但是感觉不懂操作。只打了一题,

种植方案

只需先用二进制表示每行的各个满足条件的状态,然后再将各行与它上下两行进行比较


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
int m, n, a;
int dp[1001][1001];
struct yxt
{
    int y[1001], x;
}ta[100001];
void put (int i, int t)
{
    for (int j=0; j<(1<<m); j++)
    {
        if (j&(j<<1) || (j&t)) continue ;
        else ta[i].y[++ta[i].x] = j;
    }
}
int ddp ()
{
    for (int i=1; i<=ta[1].x; i++) dp[1][i] = 1;
    for (int i=2; i<=n; i++)
    {
        for (int j=1; j<=ta[i].x; j++)
        {
            for (int k=1; k<=ta[i-1].x; k++)
            {
                if (ta[i].y[j] & ta[i-1].y[k]) continue ;
                dp[i][j] += dp[i-1][k];
            }
        }
    }
    int ans = 0;
    for (int i=1; i<=ta[n].x; i++) ans = (ans + dp[n][i])%100000000;
    return ans ;
}
int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        int t = 0;
        for (int j=1; j<=m; j++)
        {
            cin >> a;
            t = (t << 1) + (1-a);
        }
        put (i, t);
    }
    cout << ddp () << endl;
    return 0;
}