ACM-ICPC Live Archive Regionals 2014 >> Asia - Bangkok
6844 - Combination
=====

原题页面
PDF题面
Vjudge提交地址

艰辛坎坷的探索历程

设 $ {f(n)=C_{n}^{r}(n∈N^{ * },r∈[0,n])} $中奇数的个数。
题意是说，求出 $ \sum f(k),k∈[low,high] $
庞大的数据， $ n≤16\times{10^{11}}. $

step1

判断给定 $ n∈N^{ * } $时 $ C_n^r(r∈[0,n]) $的奇偶性。 不难往n,r的二进制表示方向考虑。
查阅他人博客获得结论： $ n{ & }r==r $时 $ C_n^r $为奇数。 然而本题中无需直接应用这一“定理”，所要做的是统计。
拿出纸笔推算发现，若n的二进制表示中有d个1，则 $ C_n^r(r∈[0,n]) $中存在 $ 2^d $个奇数。

step2

研究 $ f(n) $ 的递推关系及通项。 编写暴力程序 $ O(n^2) $ ，打表观察 $ n∈[0,64) $ 时 $ f(n) $ 的取值：
1
2
2 4
2 4 4 8
2 4 4 8 4 8 8 16
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 4 8 8 16 8 16 16 32 8 16 16 32 16 32 32 64
第一行 $ f(0)=1 $ 作为边界条件， 第二行 $ f(1)=2 $ ，随后各行的第k行的 $ 2^{k-2} $ 个数分别表示 $ f(2^{k-2}),f(2^{k-2}+1),…,f(2^{k-1}-1) $ 。
通过不懈的努力，观察发现从第3行开始，每行的前半部分与前一行完全一致，每行的后半部分的各个f值恰为前半部分对应位置的f值的2倍。

step3

出于数列直觉，我们尝试求解各行的和构成的数列的递推以及通项。
$ a_1=1 $
$ a_2=2 $
$ a_3=a_2+2\times{a_2}=3\times{a_2}=6 $
…
$ a_n=a_{n-1}+2\times{a_{n-1}}=3\times{a_{n-1}}(n\geq 3) $（递推公式）
通项公式:
$$
\begin{equation} a_n= \begin{cases} 1 &\mbox{$n=1$}\newline 2 &\mbox{$n=2$}\newline 2\times3^{n-2} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
\begin{equation} S_n=\sum\limits_{i=1}^{n} {a_i}= \begin{cases} 1 &\mbox{$n=1$}\newline 3 &\mbox{$n=2$}\newline 3+6\times\frac{1-3^{n-2}}{1-3}=3+3\times{(3^{n-2}-1)}=3^{n-1} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
S_n=3^{n-1}（a_n的前n项和的公式）
$$
化简后上面这个公式样子够好看了吧？

step4

再看一下第2步发现的规律，应用“二分”手段高效地求解，而且真的可以二分求解。
具体地说，就是先置求解区间 $ [l,r) $ (左闭右开)的端点于每行的头尾( $ l=2^{i-2},r=2^{i-1} $ )，利用上一步所得公式计算该区间的 $ 左端点前缀和U=\sum\limits_{k=1}^{2^{i-2}} {f(k)} $ 与 $ 右端点前缀和V=\sum\limits_{k=1}^{2^{i-1}-1} {f(k)} $ 后，不断地对区间折半，总可以确定新区间的左端点前缀和与右端点前缀和。
当区间缩至一点时， $ U==V==f(k) $，即能得到我们所求，而无需计算出[1..n]的每个函数值。

step5

以上所解决的并不是最终答案，而是前缀和 $ \sum\limits_{k=1}^{n} {f(k)} $ ；
不过走到这一步已经很好办了， $ ans=\sum\limits_{k=low}^{high} {f(k)}=\sum\limits_{k=1}^{high} {f(k)}-\sum\limits_{k=1}^{low-1} {f(k)} $

PS:写完代码后，用极大的n值测试一下，事实上 $ \sum\limits_{k=1}^{n} {f(k)} $已经超出了int64的范围。其他的细节不必多说了。

1.319s AC java代码：

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

/**
 * @date 2015-05-31
 * @author Semprathlon
 */
import java.math.*;
import java.io.*;

public class Main {
    static int maxn=42;
    static BigInteger[] sum=new BigInteger[maxn];
    static long[] Pow2=new long[maxn];
    final static BigInteger TWO=BigInteger.valueOf(2);
    final static BigInteger THREE=BigInteger.valueOf(3);
    
    static int found_pow2(long n){
        return (int)(Math.log((double)n)/Math.log(2.0));
    }

    static void init(){
        for(int i=0;i<maxn;i++)
        {
            sum[i]=THREE.pow(i);
            Pow2[i]=1L<<i;
        }
            
    }
    static BigInteger Bisearch(long l,long r,BigInteger ls,BigInteger rs,long key){
        while(l+1L<r){
            long mid=(l+r)>>1;
            if(key<mid){
                r=mid;
                rs=ls.add(rs.subtract(ls).divide(THREE));
            }
            else{
                l=mid;
                ls=ls.add(rs.subtract(ls).divide(THREE));
            }
        }
        return ls;
    }
    static BigInteger solve(long n){
        if (n<0L) return BigInteger.ZERO;
        if (n==0L) return BigInteger.ONE;
        int k=found_pow2(n+1);
        BigInteger ls=sum[k];
        BigInteger rs=sum[k+1];
        return Bisearch(Pow2[k],Pow2[k+1],ls,rs,n+1);
    }
    public static void main(String[] args) throws IOException{
        init();
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n=0,m=0;
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n=(long)in.nval;
            in.nextToken();
            m=(long)in.nval;
            if (n==0L&&m==0L) break;
            out.println(solve(m).subtract(solve(n-1)));
        }
        out.flush();
        out.close();
    }
}

0.279s AC cpp代码：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 42;
const LL mod = 1e8;
const int digit = 8;
struct LongInt
{
    LL data[3];
    LongInt()
    {
        data[0] = data[1] = data[2] = 0;
    }
    LongInt(LL n)
    {
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
    }
    LongInt operator= (const LL num)
    {
        LL n = num;
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
        return *this;
    }
    LongInt operator+ (const LL& num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] += n;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator+ (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] += b.data[0];
        tmp.data[1] += b.data[1];
        tmp.data[2] += b.data[2];
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator- (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] -= b.data[0];
        if (tmp.data[0] < 0)
        {
            tmp.data[1]--;
            tmp.data[0] += mod;
        }
        tmp.data[1] -= b.data[1];
        if (tmp.data[1] < 0)
        {
            tmp.data[2]--;
            tmp.data[1] += mod;
        }
        tmp.data[2] -= b.data[2];
        return tmp;
    }
    LongInt operator* (const LL num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] *= num;
        tmp.data[1] *= num;
        tmp.data[2] *= num;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator*= (const LL num)
    {
        *this = *this * num;
        return *this;
    }
    LongInt operator/ (const LL num)
    {
        LongInt tmp = *this;
        tmp.data[1] += tmp.data[2] % num * mod;
        tmp.data[2] /= num;
        tmp.data[0] += tmp.data[1] % num * mod;
        tmp.data[1] /= num;
        tmp.data[0] /= num;
        return tmp;
    }
    void fillzero(int n)
    {
        char str[digit * 2];
        sprintf(str, "%d", n);
        for (int i = 1; i <= digit - strlen(str); i++)
        {
            printf("%d", 0);
        }
        printf("%s", str);
    }
    void print()
    {
        if (data[2] > 0)
        {
            printf("%d", data[2]);
            fillzero(data[1]);
            fillzero(data[0]);
        }
        else if (data[1] > 0)
        {
            printf("%d", data[1]);
            fillzero(data[0]);
        }
        else
        {
            printf("%d", data[0]);
        }
    }
};

const LL pow2[maxn] = {1, 2, 4, 8, 16, 32, 64, 128,
                       256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
                       65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
                       16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
                       4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888,
                       1099511627776, 2199023255552
                      };
/*const ULL sum[maxn] = {3, 5, 11, 29, 83, 245, 731, 2189,
                       6563, 19685, 59051, 177149, 531443, 1594325, 4782971, 14348909,
                       43046723, 129140165, 387420491, 1162261469, 3486784403, 10460353205, 31381059611, 94143178829,
                       282429536483, 847288609445, 2541865828331, 7625597484989, 22876792454963, 68630377364885, 205891132094651, 617673396283949,
                       1853020188851843, 5559060566555525, 16677181699666571, 50031545098999709, 150094635296999123, 450283905890997365, 1350851717672992091, 4052555153018976269,
                       12157665459056928803
                      };*/
LongInt sum[maxn];

int found_pow2(ULL n)
{
    return int(log(n) / log(2));
}

LongInt Bisearch(LL l, LL r, LongInt ls, LongInt rs, LL key) // [ l , r ) 
{
    while (l + 1 < r)
    {
        ULL mid = (l + r) >> 1;
        if (key < mid)
        {
            r = mid;
            rs = (rs - ls) / 3 + ls;
        }
        else
        {
            l = mid;
            ls = (rs - ls) / 3 + ls;
        }
    }
    return ls;
}

LongInt solve(LL n)
{
    if (n < 0)
    {
        return 0;
    }
    if (!n)
    {
        return 1;
    }
    int k = found_pow2(n + 1);
    LongInt ls = sum[k];
    LongInt rs = sum[k + 1];
    return Bisearch(pow2[k], pow2[k + 1], ls, rs, n + 1);
}

void init()
{
    LongInt tmp = 1;
    for (int i = 0; i < maxn; i++)
    {
        sum[i] = tmp;
        tmp *= 3;
    }
}

int main()
{
    init();
    LL n, m;
    while (cin >> n >> m)
    {
        if (!n && !m)
        {
            break;
        }
        LongInt ans = solve(m) - solve(n - 1);
        ans.print();
        puts("");
    }
    return 0;
}

转载源页面
poj 3070

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

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

#define SIZE 4 
#define mod 10000

using namespace std;

struct MATRIX
{
    int mt[SIZE][SIZE];
    int x,y;
}ans,def;

int n;

inline MATRIX operator *(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=b.y;
    for(int i=1;i<=a.x;i++)
        for(int j=1;j<=b.y;j++)
            for(int k=1;k<=a.y;k++)
                c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k]%mod)*(b.mt[k][j]%mod))%mod;
    return c;
}

inline MATRIX operator +(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=a.y;
    for(int i=1;i<=c.x;i++)
        for(int j=1;j<=c.y;j++)
            c.mt[i][j]=(a.mt[i][j]+b.mt[i][j])%mod;
    return c;
}

inline bool prt(MATRIX &c)
{
    for(int i=1;i<=c.x;i++)
    {
        for(int j=1;j<=c.y;j++) printf("%d ",c.mt[i][j]);
        puts("");
    }
}

void go()
{
    n-=2;
    def.mt[1][1]=def.mt[1][2]=def.mt[2][1]=1;
    def.mt[2][2]=0; def.x=def.y=2;
    ans.mt[1][1]=ans.mt[1][2]=ans.mt[2][1]=1; ans.mt[2][2]=0;
    ans.x=ans.y=2;
    
    while(n)
    {
        if(n&1) ans=ans*def;
        def=def*def;
        n>>=1;
    }
    printf("%d\n",ans.mt[1][1]);
}

int main()
{
    while(scanf("%d",&n))
    {
        if(n==-1) break;
        else if(n==0) puts("0");
        else if(n==1) puts("1");
        else go();
    }
    system("pause");
    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 <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int MAXN = 110;
char graph[MAXN][MAXN];
bool visited[MAXN];
int nCase, cCase, use[MAXN], m, n;
 
void init() {
    memset(use, -1, sizeof(use));
}
 
void input() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%s", graph[i]);
    }
}
 
bool find(int x) {
    for (int j = 0; j < n; j++) {
        if (graph[x][j] == '1' && !visited[j]) {
            visited[j] = true;
 
            if (use[j] == -1 || find(use[j])) {
                use[j] = x;
                return true;
            }
        }
    }
    return false;
}
 
int match() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        if (find(i)) count++;
    }
    return count;
}
 
void solve() {
    printf("Case #%d: %d\n", ++cCase, match());
}
 
int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
 
    }
    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
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

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))


using namespace std;


typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;


int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};


int ans(int x)
{


  //  cout<<x<<endl ;
    if (x==-1) return 6;
    if (x==0) return 5;
    if (x==1) return 6;
    if (x==2) return 9;
    if (x==3) return 6;
    if (x==4) return 5;
    if (x==5) return 5;
    if (x==6) return 5;
    if (x==7) return 5;
    if (x==8) return 6;
}


int isleap(int y)
{
    if ((y%4==0&&y%100!=0) || y%400==0) return 366;
    else return 365;
}


int fun(int y,int m)
{
    if (m==2)
    {
        if ((y%4==0&&y%100!=0) || y%400==0) return 29;
        else return 28;
    }
    else return month[m];
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int y;
        scanf("%d",&y);
        int day=0;
        for(int i=1928;i<y;i++)
            day+=isleap(i);
        for(int i=1;i<=4;i++)
            day+=fun(y,i);
        day+=1;
        //cout<<day<<' ';
        cout<<ans(day%7)<<endl;
        /*switch (day%7)
        {
        case 0:


        }*/
    }
    return 0;
}

早就听说#define有不靠谱之处，平时写代码也对它多有抵触情绪；今日偶然一用，大跌眼镜

1

#define MAX(a,b) (a>b)?a:b

通常预处理器只对宏定义做相应的字符替换，编译器不做语法检查；visual studio 则能在替换后检查语法。
无编译错误，调用的时候无论如何都算不对

1

return MAX(Depth(T->lchild), Depth(T->rchild)) + 1;

加号的运算优先级如何处理？

出处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// WinForm.cpp: 主项目文件。

#include "stdafx.h"
#include "Form1.h"

using namespace WinForm;

[STAThreadAttribute]
int main(array<System::String ^> ^args)
{
	// 在创建任何控件之前启用 Windows XP 可视化效果
	Application::EnableVisualStyles();
	Application::SetCompatibleTextRenderingDefault(false); 

	// 创建主窗口并运行它
	Application::Run(gcnew Form1());
	return 0;
}

引用:COM线程模型详解
线程模型是一种数学模型，专门针对多线程编程而提供的算法，但也仅是算法，不是实现。本文讲解COM提出的各个类型的线程模型，再说明COM运行时期库是如何实现它们的，就像说明Windows是如何实现线程这个数学模型的一样，最后指明一下跨套间调用和各种类型套间编写的要求以帮助理解。希望读者对于Windows操作系统的线程这个概念相当熟悉，对何谓“线程安全的”亦非常了解。

　　COM线程模型

　　COM提供的线程模型共有三种：Single-Threaded Apartment（STA 单线程套间）、Multithreaded Apartment（MTA 多线程套间）和Neutral Apartment/Thread Neutral Apartment/Neutral Threaded Apartment（NA/TNA/NTA 中立线程套间，由COM+提供）。虽然它们的名字都含有套间这个词，这只是COM运行时期库（注意，不是COM规范，以下简称COM）使用套间技术来实现前面的三种线程模型，应注意套间和线程模型不是同一个概念。COM提供的套间共有三种，分别一一对应。而线程模型的存在就是线程规则的不同导致的，而所谓的线程规则就只有两个：代码是线程安全的或不安全的，即代码访问公共数据时会或不会发生访问冲突。由于线程模型只是个模型，概念上的，因此可以违背它，不过就不能获得COM提供的自动同步调用及兼容等好处了。

　　STA 一个对象只能由一个线程访问（通过对象的接口指针调用其方法），其他线程不得访问这个对象，因此对于这个对象的所有调用都是同步了的，对象的状态（也就是对象的成员变量的值）肯定是正确变化的，不会出现线程访问冲突而导致对象状态错误。其他线程要访问这个对象，必须等待，直到那个唯一的线程空闲时才能调用对象。注意：这只是要求、希望、协议，实际是否做到是由COM决定的。如上所说，这个模型很像Windows提供的窗口消息运行机制，因此这个线程模型非常适合于拥有界面的组件，像ActiveX控件、OLE文档服务器等，都应该使用STA的套间。

　　MTA 一个对象可以被多个线程访问，即这个对象的代码在自己的方法中实现了线程保护，保证可以正确改变自己的状态。这对于作为业务逻辑组件或干后台服务的组件非常适合。因为作为一个分布式的服务器，同一时间可能有几千条服务请求到达，如果排队进行调用，那么将是不能想像的。注意：这也只是一个要求、希望、协议而已。

　　NA 一个对象可以被任何线程访问，与MTA不同的是任何线程，而且当跨套间访问时（后面说明），它的调用费用（耗费的CPU时间及资源）要少得多。这准确的说都已经不能算是线程模型了，它是结合套间的具体实现而提出的要求，它和MTA不同的是COM的实现方式而已。

    COM套间

　　Apartment被翻译成套间或是单元，是线程模型的一个实现者，就像在操作系统课程中讲到的线程只是一个数学模型，而Windows的线程、进程是它（数学模型的线程、进程）的实现者。套间只是逻辑上的一个概念，实现时只是一个结构（由COM管理）而已，记录着相关信息，如它的种类（只能是上面那三个，至少现在是），并由COM根据那个结构进行相应的处理。下面说明这三种套间的实现方式：

　　STA套间 一个套间如果是STA，那么那个套间有且只有一个线程和其关联，有多个对象或没有对象和其关联，就像有多个线程和一个进程关联一样，也就是说套间那个结构和某个线程及多个对象之间有关系，关系具体是什么由COM说得算，幸运的是COM正是按照上面的线程模型来定义互相之间关系的。根据上面的算法，很容易就知道只有这个线程可以访问这个套间里的对象。

　　COM是通过在STA套间里的线程中创建一个隐藏窗口，然后外界（这个套间外的线程）对这个对象的调用都转变成对那个隐藏窗口发送消息，然后由这个隐藏窗口的消息处理函数来实际调用组件对象的方法来实现STA的规则的。之所以使用一个隐藏窗口是为了方便组件代码的编写——只需调用DispatchMessage即可将方法调用的消息和普通的消息区分开来（通过隐藏窗口的消息处理函数）。外界对这个对象的调用都将转变成对这个隐藏窗口的消息发送来实现同步。至于COM如何截获外界对对象的调用，则是利于代理对象，后面再说明。

　　值得注意的是，如果使用标准汇集法生成代理对象，则代理对象会根据是进程内还是进程外的跨套间调用，来决定具体操作。如果外界线程和STA线程在同一进程内，则代理对象将直接向STA线程中的隐藏窗口发送消息；如果不在同一进程内（包括远程进程），代理对象将向RPC管理的一个线程池请求一个线程（RPC线程）来专门向另一进程中的STA线程的隐藏窗口发送消息，而不是代理对象直接发送消息，以防止外界线程由于网络等不稳定因素而导致挂起。

　　因为COM利用消息机制来实现STA，因此STA套间里的线程必须实现消息循环，否则COM将不能实现STA的要求。

　　MTA套间 这种类型的套间可以和多个线程及多个或没有对象相关联。根据上面的MTA模型，可知只有这个套间里的线程才能访问这个套间里的对象，和STA不同的只是可以多个线程同时访问对象。

　　外界（不属于这个套间的线程）对这个套间里的对象的调用将会导致调用线程（外界线程，也就是STA线程，因为NA没有线程）挂起，然后向RPC管理的一个线程池请求一个线程（RPC线程，并已经进入了这个MTA套间）以调用那个对象的方法。对象返回后，调用线程被唤醒，继续运行。虽然可以让STA线程直接调用对象（而不用像前述的挂起等待另一个线程来调用对象），但这是必须的，因为可能会有回调问题，比如这个MTA线程又反过来回调外界线程中的组件对象（假设客户本身也是一个组件对象，这正是连接点技术），如果异步回调将可能发生错误。

　　反过来，MTA的线程访问STA里的对象时，COM将把调用转换成对STA线程里那个隐藏窗口的一个消息发送，返回后再由COM转成结果返回给MTA的线程（如果使用标准汇集法生成标准代理对象，则发生的具体情况就如上面STA套间所述）。因此STA和MTA都是只能由它们关联的线程调用它们关联的对象。而根据上面所说，当MTA调STA或STA调MTA，都会发生线程切换，也就是说一个线程挂起而换成执行另一个线程。这是相当大的消耗（需要从内核模式向用户模式转换，再倒转好几回），而NA就是针对这个设计的。

　　NA套间 这种套间只和对象相关联，没有关联的线程，因此任何线程都可以直接访问里面的对象，不存在STA的还是MTA的。

　　外界（其实就是任何线程）对这个套间里面的调用都不需要挂起等待，而是进入NA套间，直接调用对象的方法。NA套间是由COM+提供的，COM+中的每个对象都有一个环境和其相绑定，环境记录了必要的信息，并监听对对象的每一次调用，以保证当将对象的接口指针成员变量进行传递或回调时其操作的正确性（保证执行线程在正确的套间内，MTA线程就是通过将自己挂起以等待STA线程的消息处理完毕来保证的），从而避免了调用线程的挂起，因此这个代理（其实也就是环境的一部分）被称作轻量级代理（相对于STA套间和MTA套间的重量级代理——需要挂起调用线程，发生线程切换）。

　　这个轻量级代理并不是永远都不发生线程切换。当NA对象里有个对指向一个STA对象的指针的调用而调用线程不是那个STA对象关联的线程时，调用将会转成向被调用的STA对象的关联线程发送消息，此时照样会发生线程切换。同理，如果那个对象是MTA的，而调用线程是STA线程时，依旧发生线程切换。不过除此以外的大多数情况（即不在NA对象的方法中调用另一个套间对象的方法）都不会发生线程切换，即使出现上面的情况也只有必要（MTA调NA再调MTA就不用切换）才切换线程。

　　根据上面所说，STA其实和MTA逻辑上是完全一样的，只是一个是关联一个线程，一个是关联多个线程而已。但把它们分开是必要的，因为线程安全就是针对是一个线程还是多个线程。而NA之所以不关联线程是因为它的目的是消除上面跨套间调用时产生的线程切换损耗，关联线程没有任何意义。

　　COM强行规定（不遵守也没辙，因为全是COM实现套间的，根本没有插手的余地）一个进程可以拥有多个STA的套间，但只能拥有一个MTA套间和一个NA套间，我想这应该已经很容易理解了（要两个MTA套间或NA套间干甚？）。

    套间生成规则

　　线程在进行大多数COM操作之前，需要先调用CoInitialize或CoInitializeEx。调用CoInitialize告诉COM生成一个STA套间，并将当前的调用线程和这个套间相关联。而调用CoInitializeEx( NULL, COINIT_MULTITHREADED );告诉COM检查是否已经有了一个MTA套间，没有则生成一个MTA套间，然后将那个套间和调用线程相关联。接着在调用CoCreateInstance或CoGetClassObject等创建对象的函数时，创建的对象将以一个特定规则决定和哪个套间相关联（后叙）。这样完成后，就完成了线程、对象和套间的关联（或绑定）。

　　前面提到的决定对象去向的规则如下。

　　当是进程内组件时，根据注册表项InprocServer32ThreadingModel和线程的不同，列于下表：

进程内的主STA套间是进程中第一个调用CoInitialize的线程所关联的套间（即进程中的第一个STA套间）。后面说明为什么还来个进程内的主STA套间。

　　当是进程外组件时，由主函数调用CoInitializeEx或CoInitialize指定组件所在套间，与上面的相同，CoInitialize代表STA，CoInitializeEx( NULL, COINIT_MULTITHREADED );代表MTA，没有NA。因为NA是COM+提供的，而COM+服务只能提供给进程内服务器，因此只使用上面的注册表项的规则决定DLL组件是否放进NA套间，而没有提供类似CoInitializeEx( NULL, COINIT_NEUTRAL );来处理EXE组件。而且如果可以使用CoInitializeEx( NULL, COINIT_NEUTRAL );将导致调用线程和NA套间相关联了，违背了NA的线程模型，这也是为什么ThreadingModel键在InprocServer32键下。

　　跨套间调用

　　STA线程1创建了一个STA对象，得到接口指针IABCD，接着它发起STA线程2，并且将IABCD作为线程参数传入。在线程2中，调用IABCD::Abc()方法，成功或者失败天注定。由于线程2所在的STA套间不同于线程1所在的STA套间，这样线程2就跨套间调用另一个套间的对象了。按照前述的STA规则，IABCD::Abc()应该被转成消息来发送，而如果如上面做法，可以，编译通过，不过运行就不保证了。

　　COM之所以能够实现前面所说的那些规则（STA、MTA、NA），是因为跨套间调用时，被调用的对象指针是指向一个代理对象，不是组件对象本身。而那个代理对象实现前述的那三个实现算法（转成消息发送，线程切换等），而一般所说的代理/占位对象（Proxy/Stub）等其实都只是指进行汇集工作的代码（后述）。而按照上面直接通过线程参数传入的指针是直接指向对象的，所以将不能实现STA规则，为此COM提供了如下两个函数（还有其他方式，如通过全局接口表GIT）来方便产生代理：CoMarshalInterface和CoUnmarshalInterface（如果在同一进程内的线程间传递接口指针，则可以通过这两个函数来进一步简化代码的编写：CoMarshalInterThreadInterfaceInStream和CoGetInterfaceAndReleaseStream）。
现在重写上面代码，线程1得到IABCD后，调用CoMarshalInterface得到一个IStream，然后将IStream传入线程2，在线程2中，调用CoUnmarshalInterface得到IABCD，现在这个IABCD*就是指向代理对象的，而不是组件对象了。

　　因此，前面所说过的所有线程模型的算法都是通过代理对象实现的。要跨套间时，使用CoMarshalInterface将代理对象的CLSID和其与组件对象建立联系的一些必要信息（如组件对象的接口指针）列集（Marshaling）到一个IStream中，再通过任何线程间通信手段（如全局变量等）将IStream传到要使用的线程中，再用CoUnmarshalInterface散集（Unmarshaling）出接口以获得指向代理对象的接口指针。因此之所以要获得代理对象的指针是因为想使用COM提供的线程模型（但在COM+中，这不是唯一的理由），如果不想使用大可不必这么麻烦（不过后果自负），并没有强制要求必须那么做。

　　当线程1和线程2都是MTA时，则可以像最开始说的那样，直接传递IABCD*到线程2中，因为MTA线程模型同意多个线程同时直接调用对象，线程1和线程2在同一个MTA套间中，而那个对象通过某种形式（如ThreadingModel = Free）向COM声明了自己支持MTA线程模型。

　　而当a.exe的线程1和b.exe的线程2都是MTA时，则依旧需要像上面那样进行接口指针的汇集（列集→传输→散集这个过程）以得到指向代理而非对象的指针，即使线程1和线程2都是在MTA套间中，却是在两个不同的MTA套间中，因此是跨套间调用，需要汇集操作。

　　汇集代码

　　前面已经说明了套间的规则都是通过对代理对象而非组件对象发起调用以截取对组件对象的调用由代理对象来实现的。代理对象要和组件对象交互，将方法参数传递给组件对象，需要使用到汇集技术，也就是列集→传输→散集这个过程。

　　列集（Marshaling）指将信息以某种格式存为流（IStream*）形式的操作；散集（Unmarshaling）则是列集的反操作，将信息从流形式中反还出来；传输则只是流形式的传递操作。

　　这里经常发生误会。前面的CoMarshalInterface所做的列集，是将代理对象的CLSID及一些持久信息（用于初始化代理对象）格式化为一种格式（网络数据描述——Network Data Representation）后放到一个流对象中，可以通过网络（或其他方式）将这个流对象传递到客户机，由客户通过CoUnmarshalInterface从传来的流对象中反还出代理对象的CLSID和初始化用的一些持久信息，生成代理对象并使用持久信息初始化它以用于汇集操作。这就是发生误会的地方——这里的汇集操作不同于上面的汇集操作，其汇集的是接口方法的参数而不是什么CLSID和一些初始化信息。

　　因此CoMarshalInterface和CoUnmarshalInterface是用于汇集接口指针的，再准确点应该是用于生成代理对象的。代理对象应由读者自己实现，用于汇集接口方法的参数。一般有两种代理对象的实现方式：自定义汇集和标准汇集。

　　对于自定义汇集，组件需实现IMarshal接口和一个代理组件（即完全实现真正组件所有接口的一个副本，实现了汇集方法参数及线程模型的规则，也必须实现IMarshal接口），并将这个代理组件在客户机上注册，以保证代理对象的正确生成。注意：如果参数中有接口指针，必须用CoMarshalInterface和CoUnmarshalInterface进行汇集，否则无法实现正确的线程模型，且代理组件是线程模型的实现者，这点组件必须自己保证（如发送消息等）。

　　对于标准汇集，组件无需实现IMarshal接口及代理组件，代替的，组件则需要为自己生成一个代理/占位组件（Proxy/Stub），其由于可通过MIDL由IDL文件自动生成，效率高，代码的正确性有保证，因而被鼓励使用。COM提供了一个标准代理对象的实现，其通过聚合组件的代理/占位组件以表现出其好像是组件的代理对象。与自定义汇集一样，需要将这个代理/占位组件在客户机上注册以保证代理对象的正确生成。

　　至于这两种汇集的具体工作机理，由于与本文无关，在此不表，这里仅仅只为消除代理对象和代理/占位组件之间的混淆。
　　注意：对于将运行于NA套间的组件，由于COM+的强制要求，其必须使用标准汇集进行代理对象的生成而不是自定义汇集（COM+运行时期库重写了标准代理对象来截获对组件对象的调用和其自身的某些特殊处理——如保证NA套间正确工作）。

    套间实现规则

　　如前面所说，COM的套间机制要成功，必须服务器（组件）、客户和COM运行时期库三方面合力实现，其中有任何一方不按着规矩来，将不能实现套间机制的功能，不过这并不代表什么错误，套间机制不能运作并不代表程序会崩溃，只是不能和其他COM应用兼容而已。

　　比如：对象中的属性1在设计的算法中肯定不会被两个以上的线程写入，只是会被多个线程同时读出而已，因此不用同步，可以用MTA，但对象的属性2却可能被多个线程写入，因此决定使用STA。从而在客户端，通过前面说的CoMarshalInterface和CoUnmarshalInterface将对象指针传到那个只会写入对象的属性1的线程，其实这时就可以直接将对象指针传到这个线程，而不用想上面那样麻烦（而且增加了效率），但是就破坏了COM的套间规矩了——两个线程可以访问对象，但对象在STA套间中。所以？！！什么事都不会发生，因为已经准确知道这个算法不会捅娄子（线程访问冲突），即使破坏COM的规矩又怎样？！而且组件仍可以和其他客户兼容，因为不按规矩来的是客户，与组件无关。不过如果组件破坏规矩，那么它将不能和每一个客户兼容，但并不代表它和任何客户都不兼容。这里其实就是客户和组件联合起来欺骗了COM运行时期库。

　　上面的例子只是想帮助读者加深对套间的理解，实际中应该尽量保持和COM规范的兼容性（但不兼容并不代表是错误的）。客户要做的工作前面已经说过了（那两个函数或全局接口表或其他只要正确的方式），下面说明组件应该做的工作。组件可以存在于四个套间中（多了一个主STA套间），所需工作分别如下：

　　STA 当一个组件是STA时，它必须同步保护全局变量和静态变量，即对全局变量和静态变量的访问应该用临界段或其他同步手段保护，因为操作全局和静态变量的代码可以被多个STA线程同时执行，所以那些代码的地方要进行保护。比如对象计数（注意，不是引用计数），代表当前组件生成的对象个数，当减为零时，组件被卸载。此变量一般被类厂对象使用，还好ATL和MFC已经帮我们实现了缺省类厂，这里一般不用担心，但自定义的全局或静态变量得自己处理。

　　主STA 与STA唯一的不同是这是傻瓜型的，连静态和全局变量都可以不用线程保护，因为所有不是安全访问静态和全局变量的对象都通过主线程（第一个调用CoInitialize的线程）的消息派送机制运行，因此不安全的访问都被集中到了一个线程的调用中，因而调用被序列化了，也就实现了对静态和全局变量的线程保护。至于为什么是主线程，因为进程要使用STA，则一定会创建主线程，所以一定可以创建主STA。因此主STA并不是什么第四种套间，只是一个STA套间，不过关联的是主线程而已，由于它可以被用作保护静态和全局变量而被单独提出来说明。因此一个进程内也只有一个主STA套间。

　　MTA 必须对组件中的每个成员和全局及静态变量的访问使用同步手段进行保护，还应考虑线程问题，即不是简单地保护访问即可，还应注意线程导致的错误的操作，最经典的就是IUnknown::Release()。

1
2
3
4
5
6
7

DWORD IUnknown::Release()
{
 DWORD temp = InterlockedDecreament( &m_RefCount );
 if( !temp ) // 不能用m_RefCount，原因请自己思考
 delete this; // 因此不是只要用原子访问函数保护了m_RefCount的访问就行了
 return temp; // 前面对全局变量的保护也和此类似，要考虑线程问题
}

　　如果读者对自己多线程编程的技术没有信心，建议最好不要编写可以存在于MTA套间的组件，不过就不能获得MTA的高性能了。

　　在编写MTA时还应该注意到线程亲缘性（thread affinity）。没有线程亲缘性是指没有任何线程范围的成员变量，比如线程局部存储（TLS）、窗口句柄等。也就是说在MTA中不能保存任何记录着TLS内存的指针或窗口句柄，如果保存将没有意义（比如A线程记录的内存空间对B线程来说是无效的，因为TLS构造了一个线程相关的内存空间，就像每个进程都有自己的私有空间）。而不幸地MFC在它的底层运作机制的实现中大量使用了TLS，如模块线程状态、线程状态等。正是由于这个原因，MFC不能编写在MTA中运行的组件。

　　NA 由于可能会多个线程同时访问NA套间的对象，因此和MTA一样，其不能有线程亲缘性并需要保护每个成员和全局及静态变量。而关于NA的轻量级代理，是由COM+运行时期库生成的，读者完全不用操心（只需将那个组件的ThreadingModel键值赋值为“Neutral”即可）。

　　前面提到过有一种进程内组件的ThreadingModel键值可以被赋为“Both”，这种组件很像NA，哪个套间都可能直接访问它，但只是可能，而NA组件是可以，这点可以从前面的那个进程内组件所属套间的规则表中看出。这种组件可以支持一种称作自由线程汇集器（FTM——Free Threaded Marshaler）的技术，由于其与本文题目无关，在此不表。当Both的组件使用了自由线程汇集器时，除了满足MTA的要求以外（上面所说的线程安全保护和没有线程相关性），还要记录传进来的接口指针的中立形式（比如IStream*，通过CoMarshallInterface得到），以防止对客户的回调问题。

　　最后只是提醒一下，有3个STA套间，STA1、STA2和STA3。STA1用CoMarshallInterface得到的IStream*传到STA2中通过CoUnmarshalInterface得到的代理和在STA3中同样通过CoUnmarshalInterface得到的代理不同，不能混用。因为当STA2和STA3调用在STA1的对象时，STA1如果回调（连接点技术就是一种回调）调用者，则STA2和STA3的代理能分别正确的指出需要让哪个线程执行回调操作，即向哪个线程发送消息，因此不能混用。

TrueNorth：IBM的百万神经元类人脑芯片

邮票大小、重量只有几克，但却集成了54亿个硅晶体管，内置了4096个内核，100万个“神经元”、2.56亿个“突触”，能力相当于一台超级计算机，功耗却只有65毫瓦。

这就是IBM公布的最新仿人脑芯片：TrueNorth。

为什么要做TrueNorth？

因为自2008年以来，美国国防部研究机构DARPA给了IBM 5300万美元。TrueNorth是IBM参与DARPA的研究项目SyNapse的最新成果。SyNapse全称是Systems of Neuromorphic Adaptive Plastic Scalable Electronics（自适应可塑可伸缩电子神经系统，而SyNapse正好是突触的意思），其终极目标是开发出打破冯 诺依曼体系的硬件。

为什么要打破冯 诺依曼体系？

冯 诺依曼体系是传统计算机的基础。这种体系的特点是存放信息和程序指令的内存与处理信息的处理器是分离的。由于处理器是按照线序执行指令的，所以必须不断与内存通过总线反复交换信息—而这个会成为拖慢速度和浪费能量的瓶颈。尽管后来采用了多核芯片和缓存技术，但是这些只能提高速度而不能降低太多能耗，而且没办法实时处理，因为通信是瓶颈—内存和CPU的大量通信要通过总线进行。因此，近几十年来研究人员一直在致力于寻找突破原有体系的技术。

模仿大脑

模仿人类大脑是科学家寻求突破的方向。人类大脑的神经元尽管传导信号的速度很慢，但是却拥有庞大的数量（千亿级），而且每个神经元都通过成千上万个突触与其他神经元相连，形成超级庞大的神经元回路，以分布式和并发式的方式传导信号，相当于超大规模的并行计算，从而弥补了单神经元处理速度的不足。人脑的另一个特点是部分神经元不使用时可以关闭，从而整体能耗很低。

POJ 3070 矩阵乘法 模板 - proverbs - 博客园.